散列表&＃xff08;Hash table&＃xff0c;也叫哈希表&＃xff09;&＃xff0c;是根据键&＃xff08;Key&＃xff09;而直接访问在内存存储位置的数据结构。也就是说&＃xff0c;它通过计算一个关于键值的函数&＃xff0c;
将所需查询的数据映射到表中一个位置来访问记录&＃xff0c;这加快了查找速度。这个映射函数称做散列函数&＃xff0c;存放记录的数组称做散列表。
一个通俗的例子是&＃xff0c;为了查找电话簿中某人的号码&＃xff0c;可以创建一个按照人名首字母顺序排列的表&＃xff0c;在首字母为W的表中查找“王”姓的电话号码&＃xff0c;
显然比直接查找就要快得多。这里使用人名作为关键字&＃xff0c;“取首字母”是这个例子中散列函数的函数法则&＃xff0c;存放首字母的表对应散列表。关键字和函数法
则理论上可以任意确定。
它仅支持插入&＃xff0c;查找和删除三类字典操作&＃xff0c;在散列表中查找一个元素的时间在最坏的情况下是O(n)&＃xff0c;这和链表的操作时间一致。在实际中&＃xff0c;散列
的效率是非常高的&＃xff0c;最高的查找期望时间为O(1&＃xff09;
在关键字的全域U比较小时&＃xff0c;直接寻址是一种简单有效的方法。具体思路是取关键字或关键字的某个线性函数值为散列地址。即{hash(k)&＃61;k}或
{hash(k)&＃61;a*k&＃43;b}&＃xff0c;其中{a,b}为常数&＃xff08;这种散列函数叫做自身函数&＃xff09;
python语言是非常简洁的&＃xff0c;我把python源码和算法导论的伪码对比发现&＃xff0c;这伪码到python源码几乎可以算是一一对应&＃xff0c;所以&＃xff0c;我这里就贴出了
python源码&＃xff0c;即直观又简洁&＃xff1a;
KEYS &＃61; (12,6554,12345,34234,234234,6456456,34234,67645,2343432,23423,1343324)
DELETED &＃61; -1
m&＃61;len(KEYS)
T&＃61;[None for _ in range(m)]def h1(k):return k % mdef HASH_INSERT(T,k):j&＃61;h1(k) if T[j]&＃61;&＃61;None or T[j]&＃61;&＃61;DELETED:T[j]&＃61;kreturn jdef HASH_SEARCH(T,k):j&＃61;h1(k)if T[j] &＃61;&＃61; k:return jif T[j]&＃61;&＃61;None:return Nonedef HASH_DELETE(T,k):i&＃61;HASH_SEARCH(T,k)if i is None: raise Exception("key %s doesn&＃39;t exist"%k)T[i]&＃61;DELETEDif __name__&＃61;&＃61;&＃39;__main__&＃39;:for k in KEYS:HASH_INSERT(T,k)print "all keys:"print(T)print "every key:"for k in KEYS:print(k,HASH_SEARCH(T,k))print "del key1:"HASH_DELETE(T,KEYS[1])print(T)print "none keys:"for k in KEYS:if HASH_SEARCH(T,k) is None:print(k)print "insert key1:"HASH_INSERT(T,KEYS[1])print(T)
运行结果&＃xff1a;
all keys:
[234234, 12, 34234, 12345, 23423, None, 6456456, None, None, 6554, None]
every key:
(12, 1)
(6554, 9)
(12345, 3)
(34234, 2)
(234234, 0)
(6456456, 6)
(34234, 2)
(67645, None)
(2343432, None)
(23423, 4)
(1343324, None)
del key1:
[234234, 12, 34234, 12345, 23423, None, 6456456, None, None, -1, None]
none keys:
6554
67645
2343432
1343324
insert key1:
[234234, 12, 34234, 12345, 23423, None, 6456456, None, None, 6554, None]
京公网安备 11010802041100号