一、哈希表
用顺序表来存数据
存键值对时，通过哈希函数计算出键对应的索引，将值存到索引对应的数据区中
获取数据时，通过哈希函数计算出键对应的索引，将该索引对应的数据取出来
二、哈希冲突
对于任何哈希函数，都会出现两个不同的元素映射到同一个位置上的情况，这种情况称为哈希冲突
三、开链法
哈希表的每一个位置都连接一个链表，当发生冲突时，冲突的元素会被加到该位置的链表的最后
1、开链法存储数据
四、开放寻址法
如果哈希函数得到的位置i已经又数据了，那么就往后探查新的位置来存储这个值
线性探测：如果i有数据了，则探测i+1，i+2…以此类推，直到找到空的位置
1、存储值的过程
a、key=apple，cat，dog，hello，通过哈希函数映射之后得到的值都为2
b、现有一个字典dic={‘apple’:1,‘cat’:2,‘dog’:3}，存储数据，
c、原索引为2的位置没有存储数据，此时将apple的值1存储到这个
d、接着cat寻址到索引为2的位置，发现这个位置已经有值了，会继续往后探测，依次类推
2、获取值的过程
a、获取dic[‘dog’]的时候，先到索引为2的位置去获取
b、获取不到继续向后探测
3、删除值得过程
dic.remove(‘cat’)
a、给每一个节点定义一个状态
未使用
已使用
已删除
二次探测：如果位置i被占用，则探测i+1^2，i+2^2…一次类推，知道找到空的位置
五、开链法和开放寻址法的区别
开链法：
优点：删除节点比较容易，数据量比较大使用开链法
缺点：使用空间比较大
开放寻址法：
删除节点不能真正的把节点删掉，给每一个节点定义一个状态，数据量比较小使用开放寻址法
缺点：
a、使用开放寻址法,那么顺序表总归会有一天会填满
b、一般为了保证插入和查找的效率,哈希表一般在元素数量在容量的2/3时，就会进行扩容
c、扩容之后,计算的哈希函数也会随之变化,那么里面的数据存储的顺序也会变化
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/123547.html
