本帖最后由 妖精的尾巴 于 2018-5-1 23:29 编辑
很多小伙伴在面试时发现，Hashmap几乎成了面试必问内容。部分兄弟可能提前有所准备，还能应付一二，如果从来没有关注过，那可能会被面试官一套Hashmap组合拳直接打蒙。那么，这个我们日常写代码用的非常多的东西，到底有什么值得大家都来问呢？ 1.什么是Hashmap Hashmap是Java里Map接口的一个实现类，它提供了key-value的存储方式。JDK1.7及以前的版本，通过对put的key做hash运算的方法提高了插入和查找性能。1.8以后则由红黑树做了改写。我们这里仅针对1.7版本的Hashmap来做一些分析和讨论。 第一个问题，为什么要有HashMap？Map这个东西和List比，为什么会快呢？ 在回答这个问题前，首先我们来聊一下数组和链表。 数组，众所周知，在内存中是一个连续存储的区域。如 int a[] = new int[10]一般情况下，我们认为，这句Java代码会在内存中创建一块连续的区域，它的大小是10个int的长度。基于这个特点，数组在访问指定元素时，可以通过下标快速计算出元素在内存中的位置，然后获取元素的值。所以，数组获取指定元素的性能是相当不错的。但是，它的结构也有着先天性的缺点。如果我们要删除某一个指定元素，如 1，2，3，4，5，6，7，8，9，10。如果我们删除了2，那么，你可能要把3，4，5，6，7，8，9，10这些元素迁移来补空位。增加元素也是同理。 链表的实现，通常我们认为是使用指针来做，即第一个元素持有第二个元素的指针，第二个元素持有第三个元素的指针。如果用Java代码来实现，大体如下： public class Node { Object value;
Node next;
public Node(Object value) {
this.value = value; }
public static void main(String[] args) {
Node a = new Node("a");
Node b = new Node("b");
Node c = new Node("c");
a.next = b;
b.next = c;
System.out.println(a.next.next == c);
}
}由上面的代码我们不难看出，链表的特点在于内存不连续，可以通过节点间的指针操作，来快速的实现元素的插入，删除，例如下面这段代码： Node d = new Node("d");
Node temp = b.next;
b.next = d;
d.next = temp;非常简单的实现了新节点d插入到b和c之间的操作。 尽管链表和数组各有千秋，但是他们对于查找指定元素都没有什么特别好的办法，很多时候可能还是需要顺序查找（或者二分查找）,依然是O(n)的。 那有没有什么办法，可以让我们再获取指定元素的时候，速度再快一点呢？ 什么是Hashmap呢？为什么它能更快呢？ 我们定义一个新的结构，它的简易代码如下： public class MyHashMap {
Entry table[];
class Entry {
String key;
Object value;
Entry next; }}在这里为了简化演示效果，我们把key定义为String类型。可以发现，我们先定义了一个链表节点的类，然后在MyHashMap里维护了一个链表的数组。如果用图形展示，它的结构如下图： HashMap，怎么能没有Hash呢？我们来看看如何使用hash算法来做put和get。因为JDK的源码实现有了太多性能优化的地方，对于基础薄弱的同学来说，阅读难度较大，我这里写一个简单的demo，做一个演示： public class MyHashMap {
Entry table[] = new Entry[16];
class Entry {
String key;
Object value;
Entry next;
public Entry(String key, Object value) {
this.key = key;
this.value = value;
}
}
public void put(String key, Object value) {
Entry newOne = new Entry(key, value);
int hash = key.hashCode();
int index = hash & (table.length - 1);
Entry oldOne = table[index];
if (oldOne == null) {
table[index] = newOne;
} else {
Entry start = oldOne;
for (Entry curr = start; curr != null; curr = curr.next) {
if (curr.key.hashCode() == hash && ((key = curr.key) == key || key.equals(key))) {
curr.value = value;
return;
}
}
table[index] = newOne;
newOne.next = oldOne;
}
}
public Object get(String key) {
int hash = key.hashCode();
int index = hash % (table.length - 1);
Entry start = table[index];
if (start == null) {
return null; } else {
for (Entry curr = start; curr != null; curr = curr.next) {
if (curr.key.hashCode() == hash && ((key = curr.key) == key || key.equals(key))) {
return curr.value;
}
}
}
return null; }}从代码中，我们不难看出，在put元素时，我们先对key做了hash计算（这里偷懒用了String的hash），然后做一个按位与的计算，确定key在Entry数组中的位置。 如果该位置没有存放元素，我们可以直接构建元素，存放到这个位置。 但是，如果该位置已经有了元素，即table[index]!=null，我们就有了两种情况，key存在，和key不存在。有的兄弟可能会疑惑，你刚才不是对key做了比较吗？为什么这里又会有存在和不存在两种情况？ hash算法算出的结果是一个数字，假设，我们现在使用的hash算法计算出的结果是16位的，那我我们一个100位的数字，如果做hash计算，就相当于100位被压缩到了16位，肯定会丢失很多精度。如果一匹100位的数字做16位的hash输出，那么很可能回出现几个数字压缩后得到的hashcode是相同的情况，这种现象，我们叫做hash冲突。 所以，hashmap实际上，在你put元素的时，很有可能会出现，两个key，他们的hashcode一样，但是两个key的值不一样的情况。 可以通过代码看到，这我们对Entry链表做了一个简单的遍历，逐个比较每个Entry的key和我们put的key是否equals，如果相同，我们用新的value直接覆盖旧的。如果遍历一轮也没有发现雷同的key，我们直接把新的Entry放到数组里，然后把旧的节点，放到Entry.next中，从而维护了链表的连续性。 不难看出，这里Hashmap其实可以简单的想像成一个链表的数组，或者说一个二维数组。二维数组的行坐标是，是根据key的hashcode来确定，然后再横向遍历，确定具体的key到底存在不存。这个结构不难理解，但是工程中的Hashmap有很多值得我们说道的地方。 2.值得挖掘的细节 实际上，你会发现，我们初始化的Entry数组大小是有限的，只有16个位置，这里必然会出现问题。假设，我现在加入1600个元素，最理想的情况下，它也会劣化成16个链表，每个链表有100个节点。查询性能依然非常不乐观。 我们不难想象，如果，每个key进来，都能把他分配到一个全新的数组节点，不维护链表，那么，查找性能无疑是最理想的。但是，这里会面临一个扩容的问题。即，16个元素的数组，当你放入第17个元素时，我们该怎么办？ 我们看JDK的源码中，当需要扩容时，它实际上是new了一个新的数组，然后把旧数组的元素逐个拷贝到新数组中。这里就产生了一个新问题，扩容，扩多少？扩大了浪费，扩小了下次还要扩，扩的不合适，位移操作多，都很麻烦。 而Hashmap的实现中，扩容倍数是2倍。我们画个图来尝试理解下，为什么是2倍。假设我现在有一个Hashmap，它的Entry数组只有4个元素，但是我存了8个key进去，那么假设它的分部情况如下图： 假设我们现在扩容一倍，变成8个元素，那么之前的元素可能要重新计算它在数组中的位置。对于1来说，1在4个元素时排序在第一个，它在8个元素时还是排序在第一个。但是对于7来说，它在4个元素时排在第三位，在8个元素时，就需要排在第七位，但是这里有个很巧合的事情，7从3~迁移到7，刚好移动了4个位置，刚好是你扩容一倍的位置。所以，对于扩容2倍的情况来说，所有的元素，它的位置要么是不变，要么是newIndex = oldIndex + size。可以说，是非常的巧妙了。当然，实际上这里的操作是二进制的位运算，这里只是拿十进制举例，帮助部分基础差的兄弟们理解为什么要这样做，具体的实现请以源码为准。 3.看了这么多，这个东西到底有什么鸟用？ 实际上，hash散列这个思想，是非常常用的。类比一下，你就会发现很多项目场景上的问题都有可能用到： nginx负载均衡，现在我们的项目部署了3台服务器a、b、c，一个用户的请求进来后，你要确定，用户的这个请求到底该发送给三台服务器中的哪一台。 有的兄弟第一时间会想到轮询，均匀的把请求分配给3个服务器，但是这里牵扯到一个问题。假设，3台服务器（集群），都各自维护了缓存，那么，你把同一个用户的请求轮询到不同的服务器上，势必会造成缓存的浪费。 如果按照用户ID取模，又有可能产生热点问题。所以，nginx中提供了hash分配的方法。把请求中某个标识计算hash，在取模服务器数量来做分配，即避免了热点问题，也可以保证同一个标识的请求总会被分配给同一个服务器的需求。 可以说，这里是hash碰撞的一个变形应用。 同样的，这个一算法/思想的变形应用，还会出现在缓存分部，数据库分库分表的拆分等场景中。可以说，hash散列是现行code环境下，使用的非常多的一个思路，所以，也不难理解为什么大家都会问你对于Hashmap的了解。 我们学习一门语言的使用，那么它的源码（尤其Java这种自己实现自己的语言）无疑是我们最好的教材，不是说需要你对源码背的滚瓜乱熟，而是说，它里面有很多值得借鉴，学习的地方，可以扩展我们解决业务问题时的思路。 与君共勉。
| 
收藏
淘帖
踩
