java中HashMap的用法

这篇文章主要介绍“java中HashMap的用法”，在日常操作中，相信很多人在java中HashMap的用法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”java中HashMap的用法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

1、HashMap的数据结构以及如何存储数据?

HashMap的几个重要参数：
transient int size：表示当前HashMap包含的键值对数量
transient int modCount：表示当前HashMap修改次数
int threshold：表示当前HashMap能够承受的最多的键值对数量，一旦超过这个数量HashMap就会进行扩容
final float loadFactor：负载因子，用于扩容
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4：默认的table初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75f：默认的负载因子
数组的特点是：寻址容易，插入和删除困难；
而链表的特点是：寻址困难，插入和删除容易。
Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“），请看下图（横排表示数组，纵排表示数组元素【实际上是一个链表】）。 

 

从图中我们可以看到一个hashmap就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组。我们来看看java代码：

/** 
     * The table, resized as necessary. Length MUST Always be a power of two. 
     *  FIXME 这里需要注意这句话，至于原因后面会讲到 
     */  
    transient Entry[] table;  






static class Entry<K,V> implements Map.Entry<K,V> {  
        final K key;  
        V value;  
        final int hash;  
        Entry<K,V> next;  
..........  
}

上面的Entry就是数组中的元素，它持有一个指向下一个元素的引用，这就构成了链表。 
     当我们往hashmap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。从hashmap中get元素时，首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么hashmap的get效率将是最高的

hash算法 
我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。 
所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。
    确定hash数组的索引位置

方法一：
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     //可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算 速度更快
}

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高。
看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 

 
所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。 

hashmap中默认的数组大小是16
因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。 
所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：

// Find a power of 2 >= initialCapacity  
        int capacity = 1;  
        while (capacity < initialCapacity)   
            capacity <<= 1;

2、扩容机制，如何扩容，1.7扩容时出现环型链表了解吗？1.8怎么扩容的？几倍扩容？默认容量多少？

扩容机制
当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容

什么时候扩容?
1、 存放新值的时候当前已有元素的个数必须大于等于阈值：
当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75（JDK中的解释就是尽量减少rehash的次数，并且在时间和空间上做了一个很好的折中。同时，如果这个值设置的比较大的话，桶中的键值碰撞的几率就会大大上升），也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作
2、 存放新值的时候当前存放数据发生hash碰撞

resize
在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize

如何扩容？
resize()方法

 * @param newCapacity the new capacity, MUST be a power of two; 
     *        must be greater than current capacity unless current 
     *        capacity is MAXIMUM_CAPACITY (in which case value 
     *        is irrelevant).
void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);  //transfer函数的调用
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

//其实就是新建一个 newCapacity大小的数组，然后调用transfer()方法将元素复制进去。

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) { //这里才是问题出现的关键..
            while(null != e) {
                Entry<K,V> next = e.next;  //寻找到下一个节点..
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);  //重新获取hashcode
                e.next = newTable[i];  
                newTable[i] = e;
                e = next;
            }
        }

总得来说，就是拷贝旧的数据元素，从新新建一个更大容量的空间，然后进行数据复制

关于环形链表的形成，则主要在这扩容的过程。当多个线程同时对这个HashMap进行put操作，而察觉到内存容量不够，需要进行扩容时，多个线程会同时执行resize操作，而这就出现问题了，问题的原因分析如下：
首先，在HashMap扩容时，会改变链表中的元素的顺序，将元素从链表头部插入（避免尾部遍历）。
而环形链表就在这一时刻发生，以下模拟2个线程同时扩容。假设，当前hashmap的空间为2（临界值为1），hashcode分别为0和1，在散列地址0处有元素A和B，这时候要添加元素C，C经过hash运算，得到散列地址为1，这时候由于超过了临界值，空间不够，需要调用resize方法进行扩容，那么在多线程条件下，会出现条件竞争，模拟过程如下：
线程一：读取到当前的hashmap情况，在准备扩容时，线程二介入

线程二：读取hashmap，进行扩容

线程一：继续执行

这个过程为，先将A复制到新的hash表中，然后接着复制B到链头（A的前边：B.next=A），本来B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将B.next=A，所以，这里继续复制A，让A.next=B，由此，环形链表出现：B.next=A; A.next=B

1.7、1.8的区别

1.8主要优化减少了Hash冲突 ，提高哈希表的存、取效率。

• 底层数据结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构（当链表长度大于8，转为红黑树）。

• JDK1.8中resize()方法在表为空时，创建表；在表不为空时，扩容；而JDK1.7中resize()方法负责扩容，inflateTable()负责创建表。

•  1.8中没有区分键为null的情况，而1.7版本中对于键为null的情况调用putForNullKey()方法。但是两个版本中如果键为null，那么调用hash()方法得到的都将是0，所以键为null的元素都始终位于哈希表table[0]中。

• 当1.8中的桶中元素处于链表的情况，遍历的同时最后如果没有匹配的，直接将节点添加到链表尾部；而1.7在遍历的同时没有添加数据，而是另外调用了addEntry()方法，将节点添加到链表头部。

• 1.7中新增节点采用头插法，1.8中新增节点采用尾插法。这也是为什么1.8不容易出现环型链表的原因。

• 1.7中是通过更改hashSeed值修改节点的hash值从而达到rehash时的链表分散，而1.8中键的hash值不会改变，rehash时根据（hash&oldCap）==0将链表分散。

•  1.8rehash时保证原链表的顺序，而1.7中rehash时有可能改变链表的顺序（头插法导致）。

• 在扩容的时候：1.7在插入数据之前扩容，而1.8插入数据成功之后扩容。

3、Hash冲突

为什么产生Hash冲突？
由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。（两个不同的数据计算后的结果一样）

如何解决?

• 开放定址法
  从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元，然后把发生冲突的元素存入到该单元的一种方法。
  开放定址法需要的表长度要大于等于所需要存放的元素
  在开放定址法中解决冲突的方法有：
  a. 线行探查法
  线行探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。
  b. 平方探查法
  平方探查法即是发生冲突时，用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²…直到找到空闲单元。

  在实际操作中，平方探查法不能探查到全部剩余的单元。不过在实际应用中，能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元，表明此散列表太满，应该重新建立。

  c. 双散列探查法
  这种方法使用两个散列函数hl和h3。其中hl和前面的h一样，以关键字为自变量，产生一个0至m—l之间的数作为散列地址；h3也以关键字为自变量，产生一个l至m—1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长)，探查序列的步长值是固定值l；对于平方探查法，探查序列的步长值是探查次数i的两倍减l；对于双散列函数探查法，其探查序列的步长值是同一关键字的另一散列函数的值。
  开放定址法缺点：
      删除元素的时候不能真的删除，否则会引起查找错误。
      只能做一个标记，直到有下个元素插入才能真正删除该元素。

• 链地址法
  链地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链地址法适用于经常进行插入和删除的情况。

• 再哈希法
  就是同时构造多个不同的哈希函数：Hi = RHi(key) i= 1,2,3 … k;当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。

• 建立公共溢出区
  将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

到此，关于“java中HashMap的用法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！