散列表

散列表又名哈希表，这种数据结构也是在日常开发中使用非常频繁的数据结构。如Java使用HashMap，TreeMap，LinkedMap，ConcurrentHashMap 等类型都是散列表结构。

一，散列表为什么可以做到基于Key值随机访问？

散列表底层的数据结构依然是数组，如果没有数组就没有散列表。散列表的Key值相当于数组的下标，数组的下标=hash(key)，只能是大于等于0的整数。散列表的value值相当于数组下标对应的value数据。所以通过key可以直接获取其对应的value=arr[hash(key)]。

二，该如何构造散列函数，散列函数满足的基本要求？

1，散列函数得到的值应该是一个非负整数。

2，如果key1 = key2 那么 hash(key1) = hash(key2)。

3，如果key1 != key2 那么 hash(key1) != hash(key2)。

上面1和2都比较好理解，对于3要想找到一个不同的key对应散列值都不一样的散列函数，几乎是不可能的。像业界著名的MD5，SHA，CRC等哈希算法，也无法完全避免散列冲突。既然无法避免，那么如何通过其他途径解决。

三，如何解决hash冲突？

目前主要的方法有两种一种是开放寻址法，还一种是链表法。

开放寻址法又可以分为：线性探测，二次探测和双重探测。

线性探测：如果往散列表中插入数据时，如果某个数据经过散列函数之后，存储位置已经被占用，那我们从当前位置开始，依次向后寻找，第一次hash(key) + 1,第二次 hash(key) + 2。当哈希表中的数据越来越多，空闲位置越来越少时，出现冲突的可能就越大，最坏情况的时间复杂度=O(n)

二次探测：出现冲突，我们从当前位置开始，第一次hash(key) + 1^2, 第二次hash(key) + 2^2。

双重探测：出现冲突，我们从当前位置开始，使用一组散列函数，第一次hash1(key)，第二次hash2(key)。

开放寻址三种方法，当散列表中的空闲位置不多时，散列冲突的概率就会大大提高。一般情况我们会保证散列表中有一定比例的空闲空间，我们使用装载因子表示填入元素的多少。

装载因子 = 填入表中的元素 / 散列表长度

---

链表法：更加常用的解决散列冲突的办法。在散列表中，每个bucket都会对应一条链表，所有散列值相同的元素我们都放在相同bucket对应的链表中。

当插入一个元素存在冲突，或者删除一个元素时，其时间复杂度是多少呢？

链表的长度k = n/m，n表示散列中数据个数，m表示bucket的个数。所以插入和删除操作的时间复杂度就是O(k)。