HashMap之浅析

• 什么是HashMap?
  HashMap的底层结构实际上是“链表散列”，即数组和链表的结合体
  

  HashMap底层数据结构.png

• 为什么用HashMap？

1. HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)映射
2. HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改
3. HashMap是非synchronized，所以HashMap很快
4. HashMap可以接受null键和值，而Hashtable则不能（equlas()方法需要对象，HashMap是后出的API经过处理才可以）

• HashMap的工作原理
  第一，如图所示，HashMap有3个要素：hash函数+数组+单链表
  第二，对于hash函数而言，需要考虑些什么？
  要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢？显然是位运算！
  我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Node 。
  Map基本结构.png

以下是具体的put过程（JDK1.8版）
1、对Key求Hash值，然后再计算下标
2、如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）
3、如果碰撞了，以链表的方式链接到后面
4、如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
5、如果节点已经存在就替换旧值
6、如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）

以下是具体get过程(考虑特殊情况如果两个键的hashcode相同，你如何获取值对象？)
当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

Map get过程.png

• 有什么方法可以减少碰撞？

扰动函数可以减少碰撞，原理是如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这就意味着存链表结构减小，这样取值的话就不会频繁调用equal方法，这样就能提高HashMap的性能。（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode。）

使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。为什么String, Interger这样的wrapper类适合作为键？因为String是final的，而且已经重写了equals()和hashCode()方法了。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

• 对于hash函数而言，需要考虑些什么？

1. 要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢？显然是位运算！
2. 要均匀分布，较少碰撞。说白了，我们希望通过hash函数，让数据均匀分布在数组中，尽量使得每个位置上的元素数量只有一个，不希望大量数据发生碰撞，导致链表过长，遍历链表耗时。那么怎么办到呢？也是利用位运算，通过对数据的二进制的位进行移动，让hash函数得到的数据散列开来，从而减低了碰撞的概率。

我们来看看JDK1.8的源码是怎么做的（被楼主修饰了一下）

static final int hash(Object key) {
    if (key == null){
        return 0;
    }
     int h;
     h=key.hashCode()；返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      //其中n是数组的长度，即Map的数组部分初始化长度
     return  (n-1)&(h ^ (h >>> 16));
}

简单来说就是
1、高16bt不变，低16bit和高16bit做了一个异或(得到的HASHCODE转化为32位的二进制，前16位和后16位低16bit和高16bit做了一个异或)
2、(n·1)&hash=->得到下标

参考:
HashMap？面试？我是谁？我在哪

---

技术讨论 & 疑问建议 & 个人博客

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议，转载请注明出处！