数组
数组是我们比较熟悉的一种数据结构：固定大小，索引（下标）对应的槽位用以存储数据：
我们要在数组中查找一个值，比如红框圈中的 元素5 ，可以通过遍历或者排序后二分的方式达到目的。没有更快捷的查找方式了吗？显然是有的，比如Map。
我们对存 / 取动一动脑筋，还是上图的那些元素，假如我们这样存：
此时，想获取 元素5 很容易，直接array[5]就可以，但问题也同样突出，数组的length变得很大。这个例子中，最大的元素是79，还可以接受，如果最大元素是98277呢？更大呢？
我们以取余数的方式作为变通：对于元素集合{8,1,5,6,82,33}，还将这些元素放入最开始的length为6 的数组中。分别对元素除6取余，计算结果如下：
8->2 1->1 5->5 6->0 82->4 33->3
把余数作为下标，存入数组。
此时，我们想在数组中查找是否存在元素5，只需对要查找的值——元素5，按数组的length取余5%6=5，直接array[5]即可。
这里的按数组的length取余，扮演的就是散列函数的角色！
散列函数什么是散列函数？可以理解为，将元素尽可能分散的打入到数组中的函数。
散列函数有两个特征：
对同一个元素，每次计算得到的值相同。比如上面的取余函数，5%6总是等于5。
尽可能分散
同时也有两个疑问，分别看下：
问题1：数字可以取余，字符串和对象的散列函数怎么搞？字符串
字符串的本质是字符数组，字符在ascii码表上就是数字。
对象
对象是各种属性构成的，这些属性包括基本类型、字符串等等。
当然具体的算法要比取来的复杂，比如String的hashCode算法：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
没错，各种hashCode()方法，就是我们一直在聊的散列函数！
Tips:
围绕hashCode有几道经典面试题，正值跳槽季，给大家安利一下： 1.Object的hashCode是不是内存地址？ 2.什么情况下会覆写hashCode()方法？你有没有覆写过这个方法？ 3.如果对象A equals 对象B，则对象A和对象B的hashCode是否相等？反过来，对象A和对象B的hashCode值相等，equals是否返回true？问题2：不同元素的散列函数计算结果相同，怎么解决？
到目前为止，一切很顺利。length=6的数组完成了对集合{8,1,5,6,82,33}所有元素的安置，但这是最简单的情况。如果再增加一个数字，就选西方人认为不怎么吉利的 13 好了，取余计算13%6=1，原本应该放在索引为1的槽上，而我们的数组现在已经满员了。
这就是hash冲突的问题，怎么解决？显然直接覆盖并不合理，那样会丢掉原有的元素1。想想HashMap，如果发生了hash冲突，就丢弃原有值，这种做法使用者肯定无法接收。
是时候让另一种数据结构登场了——链表。
链表数组占用相邻的整块内存，且固定大小；链表则不然，由于结构上存在指向下一个节点（内存地址）的指针，因此不要求内存地址连续，大小也不固定。
因为结构的缘故，链表在插入、删除方面更有优势，修改指针指向即可；而数组在快速定位某槽位上更具优势，链表只能从头遍历。
加入链表后，散列表升级成这样：
放入 Put
元素13放入时，计算hashCode为1（姑且按取余的方式进行理解）。如果索引为1的槽位为空，直接放入元素；如果索引为1的槽位已经存在元素，将该槽位存储结构变更为链表。
获取 Get
根据Key值，计算hashCode。如果hashCode，也就是索引对应的槽位为空或只有一个元素，直接返回该值；如果hashCode对应的槽位中的数据为链表结构，对链表进行遍历，直到找到与KEY equals的对象。
如果hash冲突比较多，会发生什么情况？
链表的无限扩张，会使得查询变得缓慢，我们最初不就是想用散列表解决快速查找的问题吗？如上图这种情况，散列表几乎失去了意义，又回到了遍历查找的时代，这也是散列函数尽可能将元素均匀分布的原因。怎么解决？数组快要满时，对其扩容！
HashMap也是这么做的，初始值2^4=16的数组，默认0.75的扩容因子；当元素个数超过阈值，即16*0.75=12的时候，触发resize方法进行扩容。数组大小翻倍，元素rehash后放入相应的槽位。
可以看出，散列表就是HashMap的底层结构。当然了，JDK 1.8版本对其还有红黑树等优化，感兴趣可查阅 Java 8系列之重新认识HashMap
ok，本篇文章到此就告一段落了，下一篇我们探讨下图的经典问题——最短路径，敬请关注！
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/68919.html
摘要：什么是散列表和散列函数哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。根据键值从散列表中移除值。请实现散列表将和存在一个对象中即可定义一个包含和属性的类并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第五周的练习题，上周忘记发啦，这周是复习 Dictionary 和 Hash...
摘要：什么是散列表和散列函数哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。将字典的所有键名以数组的形式返回。根据键值从散列表中移除值。这是第五周的练习题，上周忘记发啦，这周是复习 Dictionary 和 HashTable。 下面是之前分享的链接： 1.每周一练 之 数据结构与算法（Stack） 2.每周一练 之 数据结构与算法（LinkedList） 3.每周一练 之 数据结构...
摘要：散列表结构字典与集合散列表散列表结构是字典和集合的一种实现方式。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字范围是到列表长度。即使使用一个高效的散列函数，仍然存在将两个键映射为同一个值的可能，这种现象称为碰撞。 散列表结构 字典与集合 散列表 散列表(Hash Table)结构是字典(Dictionary)和集合(Set)的一种实现方式。散列算法的作用是尽可能快...
摘要：对散列表的简单学习类也叫类，是类的一种散列表实现方式。键值散列函数散列值形成散列表地址数据键值对相关操作方法创建一个散列表实现一个散列函数，即将码值相加的方法。 对JS散列表的简单学习 HashTable类也叫HashMap类，是Dictionary类的一种散列表实现方式。 散列算法的作用是尽可能快的在数据结构中找到一个值。 在之前的学习中，如果你想要获得数据结构中的一个值，需要遍历整...
阅读 1662·2021-11-23 09:51
阅读 3116·2021-09-26 10:21
阅读 772·2021-09-09 09:32
阅读 848·2019-08-29 16:06
阅读 3278·2019-08-26 13:36
阅读 759·2019-08-26 10:56
阅读 2549·2019-08-26 10:44
阅读 1130·2019-08-23 14:04
