HashMap原理

HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

数组：存储区间连续，占用内存严重，寻址容易，插入删除困难；

链表：存储区间离散，占用内存比较宽松，寻址困难，插入删除容易；

Hashmap综合应用了这两种数据结构，实现了寻址容易，插入删除也容易。

image.png

HashMap的基本存储原理以及存储内容的组成

基本原理：先声明一个下标范围比较大的数组来存储元素，数组存储的元素是一个Entry类，这个类有三个数据域，key、value（键值对），next(指向下一个Entry)。

例如，第一个键值对A进来。通过计算其key的hash得到的index=0。记做:Entry[0] = A。

第二个键值对B，通过计算其index也等于0， HashMap会将B.next =A,Entry[0] =B,

第三个键值对 C,index也等于0,那么C.next = B,Entry[0] = C；

这样我们发现index=0的地方事实上存取了A,B,C三个键值对,它们通过next这个属性链接在一起。我们可以将这个地方称为桶。

对于不同的元素，可能计算出了相同的函数值，这样就产生了“冲突”，这就需要解决冲突，“直接定址”与“解决冲突”是哈希表的两大特点。

HashMap是基于散列法（又称哈希法hashing）的原理，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。

HashMap具体的存取过程如下：

put键值对的方法的过程是：

获取key ；
通过hash函数得到hash值；
int hash=key.hashCode(); //获取key的hashCode，这个值是一个固定的int值
得到桶号(一般都为hash值对桶数求模) ，也即数组下标int index=hash%Entry[].length。//获取数组下标：key的hash值对Entry数组长度进行取余
存放key和value在桶内。
table[index]=Entry对象；

get值方法的过程是:

获取key
通过hash函数得到hash值
int hash=key.hashCode();
得到桶号(一般都为hash值对桶数求模)
int index =hash%Entry[].length;
比较桶的内部元素是否与key相等，若都不相等，则没有找到。
取出相等的记录的value。

HashMap中直接地址用hash函数生成；解决冲突，用比较函数遍历桶内数据解决。如果每个桶内部只有一个元素，那么查找的时候只有一次比较。

如何重新调整HashMap的大小

“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

不可变对象作为key的好处

作为键的原因是 String, Interger这样的类作为HashMap的键是很合适的，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

HashMap多线程的条件竞争（死锁，在hashmap大小重新调整时有概率发生）

在并发环境下，当申请完了新的内存空间后，我们要把原来的内存空间中的数据转移到新内存空间中去。可能会形成环状链表，导致get操作时，cpu空转。

ConcurrentHashMap实现原理及源码分析

ConcurrentHashMap实现原理

我们知道HashTable是synchronized的，但是ConcurrentHashMap同步性能更好，ConcurrentHashMap可以代替HashTable。
HashTable ： HashTable和HashMap的实现原理几乎一样，差别无非是：
1.HashTable不允许key和value为null；
2.HashTable是线程安全的。
但是HashTable线程安全的策略实现代价却太大了get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，性能会非常差。

image.png

HashTable性能差主要是由于所有操作需要竞争同一把锁，而如果容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这样便可以有效地提高并发效率。这就是ConcurrentHashMap所采用的"==分段锁=="思想。

image.png

ConcurrentHashMap源码分析

ConcurrentHashMap采用了非常精妙的"分段锁"策略，ConcurrentHashMap的主体是个Segment数组。

final Segment<K,V>[] segments;

Segment继承了ReentrantLock，所以它就是一种可重入锁（ReentrantLock)。在ConcurrentHashMap，一个Segment就是一个子哈希表，Segment里维护了一个HashEntry数组，并发环境下，对于不同Segment的数据进行操作是不用考虑锁竞争的。所以，对于同一个Segment的操作才需考虑线程同步，不同的Segment则无需考虑。

Segment类似于HashMap，一个Segment维护着一个HashEntry数组

transient volatile HashEntry<K,V>[] table;

HashEntry是目前我们提到的最小的逻辑处理单元了。一个ConcurrentHashMap维护一个Segment数组，一个Segment维护一个HashEntry数组。

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
        //其他省略
}

我们说Segment类似哈希表，那么一些属性就跟我们之前提到的HashMap差不离，比如负载因子loadFactor，比如阈值threshold等等，看下Segment的构造方法

Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
            this.loadFactor = lf;//负载因子
            this.threshold = threshold;//阈值
            this.table = tab;//主干数组即HashEntry数组
        }

我们来看下ConcurrentHashMap的构造方法

public ConcurrentHashMap(int initialCapacity,
                               float loadFactor, int concurrencyLevel) {
          if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
              throw new IllegalArgumentException();
          //MAX_SEGMENTS 为1<<16=65536，也就是最大并发数为65536
          if (concurrencyLevel > MAX_SEGMENTS)
              concurrencyLevel = MAX_SEGMENTS;
          //2的sshif次方等于ssize，例:ssize=16,sshift=4;ssize=32,sshif=5
         int sshift = 0;
         //ssize 为segments数组长度，根据concurrentLevel计算得出
         int ssize = 1;
         while (ssize < concurrencyLevel) {
             ++sshift;
             ssize <<= 1;
         }
         //segmentShift和segmentMask这两个变量在定位segment时会用到
         this.segmentShift = 32 - sshift;
         this.segmentMask = ssize - 1;
         if (initialCapacity > MAXIMUM_CAPACITY)
             initialCapacity = MAXIMUM_CAPACITY;
         //计算cap的大小，即Segment中HashEntry的数组长度，cap也一定为2的n次方.
         int c = initialCapacity / ssize;
         if (c * ssize < initialCapacity)
             ++c;
         int cap = MIN_SEGMENT_TABLE_CAPACITY;
         while (cap < c)
             cap <<= 1;
         //创建segments数组并初始化第一个Segment，其余的Segment延迟初始化
         Segment<K,V> s0 =
             new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                              (HashEntry<K,V>[])new HashEntry[cap]);
         Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
         UNSAFE.putOrderedObject(ss, SBASE, s0); 
         this.segments = ss;
     }

ConcurrentHashMap
的get方法无需加锁，由于其中涉及到的共享变量都使用volatile修饰（一个线程修改变量值后，另外一个线程立即可见），volatile可以保证内存可见性，所以不会读取到过期数据。concurrentHashMap的put方法没有加锁，该put调用到Segment上的put方法时才加上锁，Segment中的put方法是加锁的。