java基础之HashMap

喜欢ヅ旅行 2022-06-08 03:37 190阅读 0赞

> 这几天看论坛里的大哥们都在说面试经历，无论小公司还是大公司，面试的内容有一个问题出现的概率极高，那就是问关于HashMap的实现原理、实现细节、底层实现之类的，我翻出了那本厚书《Java编程思想》细细的看一遍，发现之前对HashMap的认识仅仅就是put和set的调用了，尴尬。接下来结合着书和网上的博客将这个知识点梳理一下。

首先我想的是为什么面试官为什么对这个问题这么看重，在后来看书的过程中我大概知道了HashMap这个问题能考察的知识太多了，比如线程的问题、java内存模型问题、线程的可见和不可变问题、Hash的计算、链表的结构问题、以及二进制中的问题等等，所以这个问题有时候就可以看的出一个程序员的基础功底了。

--------------------

很多人说了HashMap是链表和数组的折中，既满足了数据的查找方便，也不会占用太多的空间，使用也是十分方便，下面是我画的一个简单的HashMap结构图：

![这里写图片描述][SouthEast]

从上面的图中可以看得出，HashMap其实是一个线性数组，但又不仅仅是线性数组那么简单，因为其中的值是按照键值对进行存取。

--------------------

## HashMap结构： ##

首先HashMap里面实现了一个静态内部类Entry，其重要的属性有key、value、next，从key和value中就明显的看出来Entry就是HashMap中实现键值对的一个重要的bean，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到

--------------------

## HashMap的工作原理： ##

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

--------------------

## HashMap的实现过程： ##

1、首先判断Key是否为Null，如果为null，直接查找Enrty\[0\]，如果不是Null，先计算Key的HashCode，然后经过二次Hash。得到Hash值，这里的Hash特征值是一个int值。

2、根据Hash值，要找到对应的数组啊，所以对Entry\[\]的长度length求余，得到的就是Entry数组的index。

3、找到对应的数组，就是找到了所在的链表，然后按照链表的操作对Value进行插入、删除和查询操作。

--------------------

## HashMap中的Hash计算： ##

HashMap的hash计算时先计算hashCode（）然后再进行二次hash，这里要进行二次的hash让我很不解，然后在书上找到了hash 的源码部分：

static int hash(int h) { 
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded 
        // number of collisions (approximately 8 at default load factor).
         h ^= (h >>> 20) ^ (h >>> 12);
         return h ^ (h >>> 7) ^ (h >>> 4); 
    }

从上面的源码中看不出个所以然，书中介绍的是先看HashMap是怎么通过Hash查找数据的索引的。

static int indexFor(int h, int length) {
        return h & (length-1);
    }

其中h是hash值，length是数组的长度，这个按位与的算法其实就是h%length求余，一般什么情况下利用该算法，典型的分组。例如怎么将100个数分组16组中，就是这个意思。应用非常广泛。

在做按位与操作的时候，后面的始终是低位在做计算，高位不参与计算，因为高位都是0。这样导致的结果就是只要是低位是一样的，高位无论是什么，最后结果是一样的，如果这样依赖，hash碰撞始终在一个数组上，导致这个数组开始的链表无限长，那么在查询的时候就速度很慢，又怎么算得上高性能的啊。所以hashmap必须解决这样的问题，尽量让key尽可能均匀的分配到数组上去。避免造成Hash堆积。所以源码中的函数就是解决这样的问题，叫做**链地址法**。

解决hash冲突的方法还有：**开放定址法、再哈希法、建立一个公共的溢出区**

--------------------

## 下面介绍下HashMap 各个函数的具体实现过程： ##

## —put( ) ##

public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value); //null总是放在数组的第一个链表中
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            //遍历链表
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                //如果key在链表中已存在，则替换为新value
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }
    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next
        //如果size超过threshold，则扩充table大小。再散列
        if (size++ >= threshold)
                resize(2 * table.length);
    }

源码解析：

*  首先是判断是否为null，如果是null，就单独的调用 putForNullKey 进行处理，函数的代码如下：

private V putForNullKey(V value) { 
            for (Entry<K,V> e = table[0]; e != null; e = e.next)
            { 
                if (e.key == null)
                { 
                    V oldValue = e.value;
                    e.value = value; 
                    e.recordAccess(this); 
                    return oldValue; 
                } 
            } 
            modCount++;
            addEntry(0, null, value, 0); 
            return null; 
    }
    //从代码可以看出，如果key为null的值，默认就存储到table[0]开头的链表了。然后遍历table[0]的链表的每个节点Entry，如果发现其中存在节点Entry的key为null，就替换新的value，然后返回旧的value，如果没发现key等于null的节点Entry，就增加新的节点。

*  计算key的hashcode，再用计算的结果二次hash，通过indexFor找到Entry数组的索引

> 这里看到一个个问题，如果两个key通过hash得到的index相同的时候，会发生覆盖么？
> 
> 这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个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的大致实现，我们应该已经清楚了。

*  然后遍历table\[i\]为头结点的链表，如果发现有节点的hash、key都相同的节点就替换为新的vale然后返回旧的value
 *  最后的 modCount++的作用在源码中是这样声明的，多线程的环境下访问modCount，只要modCount改变，其他线程读取到最新的值，在源码中的迭代的时候起到关键的作用使用Iterator开始迭代时，会将modCount的赋值给expectedModCount，在迭代过程中，通过每次比较两者是否相等来判断HashMap是否在内部或被其它线程修改，如果modCount和expectedModCount值不一样，证明有其他线程在修改HashMap的结构，会抛出异常。所以HashMap的put、remove等操作都有modCount++的计算。
 *  如果没有找到key的hash相同节点，就增加新的节点addEntry（），每个新添加的节点都增加到头结点，然后新的头结点的next指向旧的老节点
 *  如果HashMap大小超过临界值，就要重新设置大小，可扩容（具体实现见下面）。

## —get( ) ##

public V get(Object key) {
            if (key == null)
                return getForNullKey();
            int hash = hash(key.hashCode());
            //先定位到数组元素，再遍历该元素处的链表
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    return e.value;
            }
            return null;
    }

这段代码，它带来的问题是巨大的，千万记住,HashMap是非线程安全的，所以这里的循环会导致死循环的。为什么呢?当你查找一个key的hash存在的时候，进入了循环，恰恰这个时候，另外一个线程将这个Entry删除了，那么你就一直因为找不到Entry而出现死循环，最后导致的结果就是代码效率很低，CPU特别高。一定记住。

当在使用get（）线性搜索的时候，执行的速度会非常的慢，而HashMap因为使用了特殊的值进而大大提高了速度，这个特殊值称为散列码，它是通过对象的某些信息进而转换生成的，使用了Object中的hashCode（）方法从而进行快速的查询。

## —size( ) ##

HashMap的大小很简单，不是实时计算的，而是每次新增加Entry的时候，size就递增。删除的时候就递减。空间换时间的做法。因为它不是线程安全的。完全可以这么做。效力高。当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX\_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。

void transfer(Entry[] newTable) {
            Entry[] src = table;
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) {
                Entry<K,V> e = src[j];
                if (e != null) {
                    src[j] = null;
                    do {
                        Entry<K,V> next = e.next;
                        //重新计算index
                        int i = indexFor(e.hash, newCapacity);
                        e.next = newTable[i];
                        newTable[i] = e;
                        e = next;
                    } while (e != null);
                }
            }
    //在复制的时候数组的索引int i = indexFor(e.hash, newCapacity);重新参与计算。

--------------------

**则这里只是简单的介绍下，想更深入的理解还是对比这一部分的源码和《java编程思想》这本书慢慢的理解。只要理解了源码中的内容，大部分的问题都会迎刃而解，**下面是我在社区里总结的几个关于hashmap出现频率比较高的几个问题**：**

--------------------

*  当两个不同的键对象的hashcode相同时会发生什么?

> 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

--------------------

*  HashMap与Hashtable的区别：

> HashMap可以接受null键值和值，而Hashtable则不能。  
> Hashtable是线程安全的，通过synchronized实现线程同步。而HashMap是非线程安全的，但是速度比Hashtable快

--------------------

*  如果两个键的hashcode相同，你如何获取值对象

> HashMap在链表中存储的是键值对，找到哈希地址位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象

--------------------

*  如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办

> HashMap默认的负载因子大小为0.75，也就是说，当一个map填满了75%的空间的时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的数组，来重新调整map的大小，并将原来的对象放入新的数组中。

--------------------

*  为什么String, Interger这样的wrapper类适合作为键？

> String,  
> Interger这样的wrapper类是final类型的，具有不可变性，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

--------------------

*  ConcurrentHashMap和Hashtable的区别

> Hashtable和ConcurrentHashMap有什么分别呢？它们都可以用于多线程的环境，但是当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。

--------------------

*  HashMap的遍历

第一种:
    　　Map map = new HashMap();
    　　Iterator iter = map.entrySet().iterator();
    　　while (iter.hasNext()) {
    　　Map.Entry entry = (Map.Entry) iter.next();
    　　Object key = entry.getKey();
    　　Object val = entry.getValue();
    　　}
    　　效率高,以后一定要使用此种方式！
    第二种:
    　　Map map = new HashMap();
    　　Iterator iter = map.keySet().iterator();
    　　while (iter.hasNext()) {
    　　Object key = iter.next();
    　　Object val = map.get(key);
    　　}
    　　效率低,以后尽量少使用！

*  可是为什么第一种比第二种方法效率更高呢？这里我在网上查了以下

> HashMap这两种遍历方法是分别对keyset及entryset来进行遍历，但是对于keySet其实是遍历了2次，一次是转为iterator，一次就从hashmap中取出key所对于的value。而entryset只是遍历了第一次，它把key和value都放到了entry中，即键值对，所以就快了。

--------------------

以上就是我总结的关于HashMap的一部分知识，有什么问题望指出。

[SouthEast]: /images/20220608/a06465398e2b42968602eb2c3f270c36.png