网站 app 共同架构营销推广策划

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，复杂度O(1)

哈希表本质上是个数组，实现哈希表我们可以采用两种方法：

1、数组+链表

2、数组+二叉树

哈希函数

类似一个函数似的，给你一个值，经过某些加工得到另外一个值，就像这里的给你个人名，经过些许加工我们拿到首字母，那么这个函数或者是这个方法在哈希表中就叫做散列函数，其中规定的一些操作就叫做函数法则 

键值对，在jdk中就叫Entry

拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。 

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。