Java学习笔记之HashMap实现原理
网站首页 文章专栏 Java学习笔记之HashMap实现原理
Java学习笔记之HashMap实现原理
编辑时间:2019-05-06 18:10 作者:毛毛小妖 浏览量:231 评论数:0

一、HashMap的数据结构

HashMap是利用数组和链表/红黑树来实现对数据的存储。

1>数组

数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

2>链表

链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

3>结构图

从上图我们可以发现HashMap是由数组+链表组成的,数组中每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next。HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

二、一些概念

1>hashCode

hashCode是用于查找的,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的

2>equals

equals()作为方法,比较对象内容是否相同。

三、HashMap的存取实现

HashMap的存取使用了一个算法

// 存储时:
int hash = key.hashCode(); // 根据key获取hash值
int index = hash % Entry[].length; // 获取数组下标
Entry[index] = value; // 存放key和value

// 取值时:
int hash = key.hashCode(); // 根据key获取hash值
int index = hash % Entry[].length; // 获取数组下标
return Entry[index]; // 获取key和value

1>put

疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?

HashMap中的Entry类里面有一个next属性,指向下一个Entry。也就是说数组中存储的是最后插入的元素,每个index处的Entry是一个链表结构,所有index相同的Entry会通过链表的方式链在一起。

源码如下:

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);
}

2>get

从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

源码如下

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;
}

3>map大小

Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因子,随着map的size越来越大,Entry[]会以一定的规则加长长度。

四、jdk1.8的改进

jdk1.8以后采用的是数组+链表/红黑树。当hash值对应的链表节点大于8时,自动转换为红黑树存储,优化存储速度,时间复杂度为O(lgn),而链表的时间复杂度始终为O(n)。

五、总结

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

当两个不同的键对象的hashcode相同时会发生什么? 它们会储存在同一个位桶的LinkedList中。利用键对象的equals()方法用来找到键值对。

推荐文章
来说两句吧
最新评论
    还没有人评论哦,快来坐沙发吧!