python 哈希表——拉链法

哈希表是一种对链表的应用，可用以模拟集合方法。具体原理过多，就不一个一个地讲解。

1.  
   class Linklist:##创建哈希表节点
2.  
   class Node:#创建链表节点
3.  
   def __init__(self,item=None):
4.  
   self.item=item
5.  
   self.next=None
6.  
    
7.  
   class Linklist_iterator:##创建迭代器类
8.  
   def __init__(self,node):
9.  
   self.node=node
10.  
    def __next__(self):##迭代器
11.  
    if self.node:
12.  
    cur_node=self.node
13.  
    self.node=cur_node.next
14.  
    return cur_node.item
15.  
    else:
16.  
    raise StopIteration
17.  
    def __iter__(self):##循环调用__next__方法
18.  
    return self
19.  
     
20.  
     
21.  
    def __init__(self):
22.  
    self.head=None
23.  
    self.tail=None
24.  
     
25.  
    def find(self,obj):
26.  
    for n in self:
27.  
    if n==obj:
28.  
    return True
29.  
    else:
30.  
    return False
31.  
     
32.  
    def append(self,obj):
33.  
    s=Linklist.Node(obj)
34.  
    if not self.head:
35.  
    self.head=s
36.  
    self.tail=s
37.  
    else:
38.  
    self.tail.next=s
39.  
    self.tail=s
40.  
     
41.  
     
42.  
    def __iter__(self):##创建迭代器
43.  
    return self.Linklist_iterator(self.head)
44.  
     
45.  
    def __repr__(self):##将对象用字符串的方式描述
46.  
    return "<<" ",".join(map(str,self)) ">>"
47.  
     
48.  
    class HAXI:##创建哈希表
49.  
    def __init__(self,size=10):
50.  
    self.size=size
51.  
    self.T=[Linklist()for _ in range(self.size)]
52.  
    def h(self,k):##自定义的哈希函数
53.  
    return k%self.size
54.  
    def find(self,k):##查找
55.  
    i=self.h(k)
56.  
    return self.T[i].find(k)
57.  
    def insert(self,k):##插入
58.  
    i=self.h(k)
59.  
    if not self.find(i):
60.  
    self.T[i].append(k)
61.  
    else:##集合中没有重复的元素
62.  
    print("重复插入")
63.  
    haxi=HAXI()
64.  
    for i in range(13):
65.  
    haxi.insert(i)
66.  
     
67.  
    print(",".join(map(str,haxi.T)))
68.  
    print(haxi.T)

运行结果：

这篇好文章是转载于：学新通技术网