字典与哈希表（HashMap）

哈希表又称散列表，是根据关键码值而直接进行访问的数据结构，即通过关键码将值映射到表中的某个位置来存储和访问，以加快查找的速度。哈希表是字典的实现原理，字典通过哈希表来存储数据，而读取的时候也是通过哈希表来获取对应的值。无论哈希表中有多少数据，增删操作的时间复杂度都为O(1),相当于无须查找，直接定位对其操作。

哈希表的存储方式是以数组为基础，每个元素是一个链表，链表上的元素的查找是根据特定的哈希算法决定的，并尽量避免哈希冲突。

如何减少和希函数产生的冲突？

• 需要将哈希函数的返回数据在哈希表中的位置尽可能的分布均匀，避免集中在某些数组中。
• 当冲突产生时需要更快更方便的方式来解决冲突，提供再深一级的哈希码。
• 每组中应保持适当的链表个数，并控制出发扩容的装填因子α = 填入链表中的数据个数 / 链表的总数。装填因子一是控制扩容，二是避免哈希冲突。

哈希表解决冲突的方案：

开放定制法

三种：线性探测再散列、平方探测再散列、随机探测再散列

（表格解释：从前向后插入数据，如果插入位置已经占用，发生冲突，冲突的另起一行，计算地址，直到地址可用，后面冲突的继续向下另起一行。最终结果取最上面的数据（因为是最“占座”的数据））

avatar

链地址法

产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据
上面的例子，用链地址法则是下面这样：

avatar

没找到想要的？点击
参考HashMap 查看更多HashMap精讲