哈希表一直都是一个很重要的数据结构,从上大学开始,一直有听闻,面试题也有相当的涉及,接下来继续扫盲。

哈希表

哈希表根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值通过哈希函数映射到表中一个位置来访问记录,以加快查找的速度。

哈希表的工作原理如下

首先拿到key值,通过哈希函数将key值转化为数组的下标,在插入元素之前,判断该下标位置上是否已经存在元素,若已经存在元素则称为collision(碰撞)。

当元素发生碰撞时,存在很多方法来处理这种碰撞,常用的方法有链接法(java hashmap的实现),每一个index位置连一个链表,用来存储发生碰撞的元素。

另一种解决碰撞的方法为开放寻址法(python中dict的实现)。

开放寻址法指当前位置发生了碰撞,采用某种方法(线性,二次,双倍散列)对哈希表中其他位置进行访问。如果哈希表全都装满了则需要对哈希表进行扩容。

python 中dict常用方法

遍历操作:

1
2
3
for i in dicts:
print(i)
print(dicts[i])

删除操作:

1
2
3
dicts.pop(key)
dicts.popitem() #删除最后一个加入的元素
del dicts #直接删除元素