散列表，也叫做哈希表。
它基于数组的随机访问的特性，来拓展延伸，从而实现了散列表，为什么这样说呢，我们举一个例子来看看。
假设学校举行运动会，对100个进行编号，我们现在希望实现通过编号来快速找到某一个学生，该怎么实现呢，我们可以维护一个数组，将每一个学生的编号放到同样的数组下标内，比如1号放到数组下标为1的位置，接下来额以此类推，这样就能够实现快速随机访问，在O(1)的时间复杂度内就找到这个学生。
也许这样你看不出用到了散列思想，但这确实就是使用了散列的思想，将数组下标和学生编号进行了映射，只不过映射规则非常简单，就是f(n) = n。
但是现实时不会这么简单的，现在要求编号要复杂一点，用 6 位数字来表示。比如 051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位还是原来的编号 1 到 89。这个时候我们该如何存储选手信息，才能够支持通过编号来快速查找选手信息呢？
依然时通过散列的思想，我们可以截取编号的后两位作为数组下标，存储选手信息，当我们要查询时，也截取后两位作为数组下标，到数组内去查询，这样就能够实现快速查询。
其中，参赛选手的编号我们叫作键（key）或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）。拿上面那个来说，关键字是051167，我们通过hash函数，即截取后两位，计算得到hash值67。
int hash(String key) {
// 获取后两位字符
string lastTwoChars = key.substr(length-2, length);
// 将后两位字符转换为整数
int hashValue = convert lastTwoChas to int-type;
return hashValue;
}
可以看到的是，hash函数是一个非常重要的东西，如何构造一个好的hash函数也是非常重要的，通过学习，我目前知道的是3点：
1：hash值是一个非负整数
2：如果key1==key2 hash(key1) == hash(key2)
3：如果key1!=key2 hash(key1) != hash(key2)
第一点很好理解，因为我们要维护成数组的下标，那么负数和非整数都是不行的；第二点也好理解，如果两个key相同，那么经过同一个hash函数计算，他们得到的值也必须要一样。第三点要好好理解一下，不同的key得到的hash值不一样，也就是这一点，引出了hash冲突这样一个概念。
因为即使最好的hash算法，也无法保证两个不一样的key得到的hash值一定不一样。
计既然无法解决，那么就要找其他的方法了。
经典的方法有链表法和开放寻址法。
开放寻址法：
这个比较好理解，就是如果计算得到的hash值在数组内已经有数据了，那我们就在紧接下一个寻找，如果没有数据，就插入到这个位置，这种方法不是非常好。
你可能已经发现了，线性探测法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。
为了保证散列表的性能，我们会维护一个装载因子的概念。
装载因子：填入表中的元素个数 / 散列表的长度
装载因子越小，发生散列冲突的概率就越小，性能就越好，如果装载因子越大，那么性能就会迅速下降，不过装载因子越小，那么需要消耗的内存就越大，如果不考虑性能，装载因子可以超越1.
链表法：
链表法比较常用
链表法
介绍了散列表的基本概念和一些散列冲突的解决方法，拿我们来看看究竟怎么样，才能设计一个优秀的企业级的散列表呢？
设计散列表，最关键的就是散列函数的设计，一个好的散列函数，既能够快速计算，也能够让散列冲突的概率较为小。既然要计算快速，那么这个散列函数就必然不能够太复杂，不然计算时间就较为耗时，其次也要保证计算出来的hash值要平均分布，否则一个槽出现的概率非常大，那么散列冲突的概率就大大提升。
我们之前说过，hash函数是有一个装载因子的概念的，对于动态的散列表，我们不断进行插入操作，它的装载因子势必会扩大，当装载因子过大时，hash表的性能就会下降，这个时候，就需要对hash表进行扩容，这样装载因子就会下降，对于数组的扩容，我们都可以很好的实现，不过对于散列表的扩容，就不是简单的移动数据这么简单了。
hash扩容
可以看到，当我们新建了一个数组后，原来hash表中的内容就要重新计算hash值，然后存放到新的哈市、表中，并不是简单的移动就能解决的。
不过，这样扩容，如果数据量很大，那么效率就必然很低下，怎么解决呢，我们可以不立刻拷贝数据到新的hash表里面，可以每新插入一个数据就将老的表里面的数据拿一个到新的表里面，这样就可以不一次性拷贝数据，效率就会得到提升。
高效hash扩容
接下啦看如何选择合适的hash冲突解决法：
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
工业级散列表举例分析刚刚我讲了实现一个工业级散列表需要涉及的一些关键技术，现在，我就拿一个具体的例子，Java 中的 HashMap 这样一个工业级的散列表，来具体看下，这些技术是怎么应用的。
1. 初始大小HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。
2. 装载因子和动态扩容最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
3. 散列冲突解决方法HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能。
于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
4. 散列函数散列函数的设计并不复杂，追求的是简单高效、分布均匀。我把它摘抄出来，你可以看看。
int hash(Object key) {
int h = key.hashCode()；
return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}
其中，hashCode() 返回的是 Java 对象的 hash code。
比如 String 类型的对象的 hashCode() 就是下面这样：
public int hashCode() {
int var1 = this.hash;
if(var1 == 0 && this.value.length > 0) {
char[] var2 = this.value;
for(int var3 = 0; var3 < this.value.length; ++var3) {
var1 = 31 * var1 + var2[var3];
}
this.hash = var1;
}
return var1;
}
网友评论