什么是哈希表?
哈希表也叫散列表，是一个根据键(key)直接访问在内存存储位置的数据结构
通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这种方式加快了查找速度。而这个映射函数称作散列函数，存放记录的数组称作散列表
本质上来说是个数组，实现哈希表的两种方式：
- 数组+链表
- 数组+二叉树
一般数组里存放的是单一的数据，而哈希表中存放的是键值对
数据经过散列函数计算之后，放到特定的位置
entry就是键值对，只是不同的叫法
哈希冲突
数据经过散列函数计算之后，指定在同一个位置上，就是哈希冲突
处理哈希冲突
1.开放寻址法
当计算出来的位置已经有数据了，就顺着位置往后找没有数据的位置放数据
2.拉链法
在原来的entry中额外保存一个next指针，指向数组的另外一个位置放置新数据
哈希表的扩容
当哈希表被占用的位置比较多的时候，出险冲突的概率也就变高了，就会进行扩容
哈希表的扩容不是简单的扩大，而是新创建一个数组是原来的2倍，然后把原来数组的所有entry都重新经过新的哈希函数计算一边再存放到新的位置上
哈希表如何读取数据
- 通过key利用哈希函数得出位置，然后去对应位置拿出数据，比较key，如果不对则根据next对比下一个位置的key
- 开放寻址法则是按顺序去下一个位置对比
网友评论