集合详解(四)----HashSet和HashMap源码剖析(JDK1.7)

HashSet


当初始化一个HashSet的时候,HashSet的底层实现其实是HashMap:

private transient HashMap<E,Object> map;

public HashSet() {
        map = new HashMap<>();
}

在每一个方法里面都是会通过map去调用HashMap的方法来实现。那么map是键值对类型的,那在HashSet中是怎么添加数据的呢?下面是HashSet中的添加方法。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

put的时候,e是要保存的key值,那后边的final变量呢是什么?

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

Dummy的意思就是‘虚假的’意思,也就是说当使用add方法将对象添加到Set当中时,实际上是将该对象作为底层所维护的Map对象的key,而value则都是同一个Object对象(该对象我们用不上)。

HashMap


HashMap在初始化的时候,会制定初始容量(16)和加载因子(扩容临界值0.75,意思就是当容量达到10*0.75=12的时候就会扩容):

//默认初始化化容量,即16  
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//默认装载因子  
static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap(int initialCapacity, float loadFactor) {//可手动设置初始容量和装载因子的构造器  
       if (initialCapacity < 0)  //参数有效性检查  
           throw new IllegalArgumentException("Illegal initial capacity: " +  
                                              initialCapacity);  
       if (initialCapacity > MAXIMUM_CAPACITY)  //参数有效性检查 
           initialCapacity = MAXIMUM_CAPACITY;  
       if (loadFactor <= 0 || Float.isNaN(loadFactor))  //参数有效性检查 
           throw new IllegalArgumentException("Illegal load factor: " +  loadFactor);  
       // Find a power of 2 >= initialCapacity  
       //找出“大于initialCapacity”的最小的2的幂  
       int capacity = 1;  
       while (capacity < initialCapacity)  
           capacity <<= 1;  
       this.loadFactor = loadFactor;  
       threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  
       //初始化桶数组  
       table = new Entry[capacity];  
       useAltHashing = sun.misc.VM.isBooted() &&  
               (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);  
       init();//一个钩子函数,默认实现是空  
   } 

//通过扩容因子构造HashMap,容量去默认值,即16  
public HashMap(int initialCapacity) {  
       this(initialCapacity, DEFAULT_LOAD_FACTOR);  
   }  

//使用默认的初始容量和默认的加载因子构造HashMap      
public HashMap() {
    //制定初始容量和加载因子
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}


//通过其他Map来初始化HashMap,容量通过其他Map的size来计算,装载因子取0.75  
public HashMap(Map<? extends K, ? extends V> m) {  
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,  
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  
        inflateTable(threshold);//初始化HashMap底层的数组结构  
        putAllForCreate(m);//添加m中的元素  
    }  

在HashMap的内部通过Entry数组来保存键值对,那个这个Entry是怎么实现的呢?

static class Entry<K,V> implements Map.Entry<K,V> {//实现Map.Entry接口  
       final K key;//键,final类型,不可更改/  
       V value;//值  
       Entry<K,V> next;//HashMap通过链表法解决冲突,这里的next指向链表的下一个元素  
       int hash;//hash值  
       /** 
        * Creates new entry. 
        */  
       //构造器需指定链表的下一个结点,所有冲突结点放到一个链表上  
       Entry(int h, K k, V v, Entry<K,V> n) {  
           value = v;  
           next = n;  
           key = k;  
           hash = h;  
       }  
       public final K getKey() {  
           return key;  
       }  
       public final V getValue() {  
           return value;  
       }  
       //允许设置value  
       public final V setValue(V newValue) {  
           V oldValue = value;  
           value = newValue;  
           return oldValue;  
       }  
       public final boolean equals(Object o) {  
           if (!(o instanceof Map.Entry))  
               return false;  
           Map.Entry e = (Map.Entry)o;  
           //保证键值都相等  
           Object k1 = getKey();  
           Object k2 = e.getKey();  
           if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
               Object v1 = getValue();  
               Object v2 = e.getValue();  
               if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                   return true;  
           }  
           return false;  
       }  
       public final int hashCode() {//键为空则hash值为0,否则通过通过hashcode计算  
           return (key==null   ? 0 : key.hashCode()) ^  
                  (value==null ? 0 : value.hashCode());  
       }  
       public final String toString() {  
           return getKey() + "=" + getValue();  
       }  
       /** 
        * This method is invoked whenever the value in an entry is 
        * overwritten by an invocation of put(k,v) for a key k that's already 
        * in the HashMap. 
        */  
       void recordAccess(HashMap<K,V> m) {  
       }  
       /** 
        * This method is invoked whenever the entry is 
        * removed from the table. 
        */  
       void recordRemoval(HashMap<K,V> m) {  
       }  
   }  

HashMap内部数组存储的是键值对,也就是Entry对象,Entry对象保存了键、值,并持有一个next指针指向下一个Entry对象(HashMap通过链表法解决冲突): 我们都知道HashMap是通过数组来存储的,那如何通过链表法来解决冲突的呢?举个栗子,定义一个HashMap,当调用put的时候,会根据key的hashCode值计算出一个位置,也就是要存储在数组中的位置,如果这个位置没有对象,就将该对象直接放进数组中:

如果该位置已经有对象了,则顺着此存在的对象的链开始寻找(Entry类有一个Entry类型的next成员变量,指向了该对象的下一个对象):

如果此链上有对象的话,就去使用equals方法进行比较,如果对此链上某个对象的equals方法比较为false,就把改对象放到数组中,将数组中该位置以前存在的那个对象链接到次对象的后面。

HashMap存值的时候,遵循的是LRU(Least Recently Used)算法,就是最近最少使用,意思就是系统认为最近使用的值可能会被系统经常用到,而添加的早的值用到的几率会小。

着重的说一说HashMap核心的东西,就是HashMap在存数据的时候,也就是当你进行put操作的时候,HashMap是如何来进行存的。

//添加元素  
    public V put(K key, V value) {  
        if (table == EMPTY_TABLE) {//如果底层表为空,则初始化  
            inflateTable(threshold);  
        }  
        if (key == null)//如果key为空,则执行空的逻辑  
            return putForNullKey(value);  
        int hash = hash(key);//获取key的Hash值  
        int i = indexFor(hash, table.length);//定位Hash桶  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);//调用value的回调函数,其实这个函数也为空实现  
                return oldValue;  
            }  
        }  

        modCount++;//更新修改次数  
        addEntry(hash, key, value, i);//添加到对应Hash桶的链接表中  
        return null;  
    } 


//添加key为空的元素,key为null的元素添加到第0号Hash桶中  
    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;  
    }   

不允许两个键相同,如果相同,则后插入的键所对应的值会覆盖掉之前的值。 HashMap是通过调用hash()方法获得键的hash值,并通过indexFor方法找到实际插入位置,具体的代码如下:

final int hash(Object k) {//根据键生成hash值  
        int h = 0;  
        if (useAltHashing) {  
            if (k instanceof String) {  
                return sun.misc.Hashing.stringHash32((String) k);  
            }  
            h = hashSeed;  
        }  
        h ^= k.hashCode();  
        h ^= (h >>> 20) ^ (h >>> 12);  
        return h ^ (h >>> 7) ^ (h >>> 4);  
    }  
//根据hash值计算键在桶数组的位置  
    static int indexFor(int h, int length) {  
        return h & (length-1);//由put方法可知,这个length就是数组长度,而且由构造器发现数组长度始终为2的整数次方,那么这个&操作实际上就是是h%length的高效表示方式,可以使结果小于数组长度.  
    }  

put方法通过addEntry方法将键值插入到合适的位置,当容量查过阈值(threshold)时,会发生扩容,扩容一倍。

void addEntry(int hash, K key, V value, int bucketIndex) {  
        if ((size >= threshold) && (null != table[bucketIndex])) {//容量超过阈值  
            resize(2 * table.length);//数组扩容为原来的两倍  
            hash = (null != key) ? hash(key) : 0;  
            bucketIndex = indexFor(hash, table.length);  
        }  
        createEntry(hash, key, value, bucketIndex);  
    }  
    void createEntry(int hash, K key, V value, int bucketIndex) {  
        Entry<K,V> e = table[bucketIndex];//获取原来在该位置上的Entry对象  
        table[bucketIndex] = new Entry<>(hash, key, value, e);//将当前的键值插到该位置,并作为链表的起始结点。其next指针指向先前的Entry  
        size++;  
    }  

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);//将原数组中所有键值对转移至新数组  
        table = newTable;  
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);  
    }  
void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;  
        for (Entry<K,V> e : table) {//需遍历每个Entry,耗时  
            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);  
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            }  
        }  
    }  

扩容操作需要开辟新数组,并对原数组中所有键值对重新散列,非常耗时。我们应该尽量避免HashMap扩容。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

百炼OJ 2972 2973

一、2972相邻数字的基数等比:确定进制      所谓基数等比就是后一个数与前一个数有倍数的关系。如 111 = 1 + 1 * 2(1 + 2 * 1); ...

24880
来自专栏郭耀华‘s Blog

剑指offer第六天

29.最小的K个数 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 解法一: Part...

28460
来自专栏互扯程序

Java集合深度解析之HashMap

HashMap简介 HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增...

38150
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

12240
来自专栏Java爬坑系列

【Java入门提高篇】Day24 Java容器类详解(七)HashMap源码分析(下)

13430
来自专栏微信公众号:Java团长

从代码层读懂 Java HashMap 的实现原理

Hashmap继承于AbstractMap,实现了Map、Cloneable、Java.io.Serializable接口。它的key、value都可以为nul...

10920
来自专栏向治洪

从代码层读懂HashMap的实现原理

概述  Hashmap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。它的key、value都可以...

33480
来自专栏LeetCode

LeetCode 46 & 47. Permutations I&II

Given a collection of distinct integers, return all possible permutations.

29900
来自专栏向治洪

HashMap原理解析

1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。       数组 数组存储区间是连续的,占用内存严...

20090
来自专栏cmazxiaoma的架构师之路

通过分析LinkedHashMap了解LRU

我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过,那么将来访问的几率也更高。在这里提一下,Redis缓存...

18030

扫码关注云+社区

领取腾讯云代金券