转载

coding++:jdk1.7 HashMap 的get()和put() 源码

HashMap的概述:

基于哈希表的 Map 接口的实现。

此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。

(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)

此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

         此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。

迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。

所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

         HashMap 的实例有两个参数影响其性能:初始容量 和 加载因子。

容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。

加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。

当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

         通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。

加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。

在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。

如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。

        如果很多映射关系要存储在 HashMap 实例中,则相对于按需执行自动的 rehash 操作以增大表的容量来说,使用足够大的初始容量创建它将使得映射关系能更有效地存储。

注意:此实现不是同步的。如果多个线程同时访问一个哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须 保持外部同步。

(结构上的修改是指添加或删除一个或多个映射关系的任何操作;仅改变与实例已经包含的键关联的值不是结构上的修改。)

这一般通过对自然封装该映射的对象进行同步操作来完成。

如果不存在这样的对象,则应该使用 Collections.synchronizedMap 方法来“包装”该映射。

最好在创建时完成这一操作,以防止对映射进行意外的非同步访问,如下所示:

Map m = Collections.synchronizedMap(new HashMap(…));

由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。

因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险。

注意:迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。

快速失败迭代器尽最大努力抛出 ConcurrentModificationException。

因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。

此类是 Java Collections Framework 的成员。

HashMap的桶(容量):

 // 默认的初始桶(容量)是16,每次扩容都是x2
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 // 最大容量为(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换) 
    static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子为0.75,
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 resize 操作(即扩容)。

下面说下加载因子,如果加载因子越大,对空间的利用更充分,但是查找效率会降低(链表长度会越来越长);如果加载因子太小,那么表中的数据将过于稀疏(很多空间还没用,就开始扩容了),对空间造成严重浪费。

如果我们在构造方法中不指定,则系统默认加载因子为0.75,这是一个比较理想的值,一般情况下我们是无需修改的。

另外,无论我们指定的容量为多少,构造方法都会将实际容量设为不小于指定容量的2的次方的一个数,且最大值不能超过2的30次方。

HashMap的key和value可以为null:

get():

  // 获取key对应的value 
 public V get(Object key) {
        if (key == null)
            //如果key为null,调用getForNullKey()
            return getForNullKey();
        //key不为null,调用getEntry(key);
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
}
 //当key为null时,获取value
    private V getForNullKey() {
        if (size == 0) {
            return null;//链表为空,返回null
        }
    //链表不为空,将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置!
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

//key不为null,获取value
final Entry<K,V> getEntry(Object key) {
        if (size == 0) {//判断链表中是否有值
         //链表中没值,也就是没有value
            return null;
        }
       //链表中有值,获取key的hash值 
        int hash = (key == null) ? 0 : hash(key);
        // 在“该hash值对应的链表”上查找“键值等于key”的元素 
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //判断key是否相同
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;//key相等,返回相应的value
             }
        return null;//链表中没有相应的key
    }

首先,如果key为null,则直接从哈希表的第一个位置table[0]对应的链表上查找。

记住,key为null的键值对永远都放在以table[0]为头结点的链表中,当然不一定是存放在头结点table[0]中。

如果key不为null,则先求的key的hash值,根据hash值找到在table中的索引,在该索引对应的单链表中查找是否有键值对的key与目标key相等,有就返回对应的value,没有则返回null。

put():

  // 将“key-value”添加到HashMap中 
  public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)// 若“key为null”,则将该键值对添加到table[0]中。 
            return putForNullKey(value); 
      // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 
        int hash = hash(key);//获取key的hash值
        int i = indexFor(hash, table.length);
        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))) {
             // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
   // 若“key”对应的键值对不存在,则将“key-value”添加到table中 
        modCount++;
   //将key-value添加到table[i]处
        addEntry(hash, key, value, i);
        return null;
    }

如果key为null,则将其添加到table[0]对应的链表中,putForNullKey的源码如下

// putForNullKey()的作用是将“key为null”键值对添加到table[0]位置 
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;
            }
        }
 // 如果没有存在key为null的键值对,则直接添加到table[0]处! 
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

如果key不为null,则同样先求出key的hash值,根据hash值得出在table中的索引,而后遍历对应的单链表,如果单链表中存在与目标key相等的键值对,

则将新的value覆盖旧的value,比将旧的value返回,如果找不到与目标key相等的键值对,或者该单链表为空,调用addEntry()方法将该键值对插入到改单链表的头结点位置(每次新插入的节点都是放在头结点的位置).

如果key为null,调用putForNullKey(),直接去遍历table[0]Entry链表,寻找e.key==null的Entry或者没有找到遍历结束。

如果找到了e.key==null,就保存null值对应的原值oldValue,然后覆盖原值,并返回oldValue

如果在putForNullKey()中,在table[0]Entry链表中没有找到也会调用addEntry方法添加一个key为null的Entry。

下面是addEntry的源码:

void addEntry(int hash, K key, V value, int bucketIndex) {
 //先判断大小   
  if ((size >= threshold) && (null != table[bucketIndex])) {
 // 若HashMap的实际大小不小于 “阈值”,则调整HashMap的大小    
            resize(2 * table.length);//扩容,每次增长2倍
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
       createEntry(hash, key, value, bucketIndex);//新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。 
}
void createEntry(int hash, K key, V value, int bucketIndex) {
      // 保存“bucketIndex”位置的值到“e”中 
        Entry<K,V> e = table[bucketIndex];
    // 设置“bucketIndex”位置的元素为“新Entry”,  
    // 设置“e”为“新Entry的下一个节点”  
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;

注意这里new Entry<>()的构造方法,将key-value键值对赋给table[bucketIndex],并将其next指向元素e,这便将key-value放到了头结点中,并将之前的头结点接在了它的后面。

该方法也说明,每次put键值对的时候,总是将新的该键值对放在table[bucketIndex]处(即头结点处)。

同时也要注意,这个方法首先会判断是否要扩容,当现在的HashMap中的Entry数大于等于扩容临界值(capacity*load factor)并且index对应的地方没有Entry就扩容.HashMap每次扩容的大小为2倍原容量,

默认容量为16,hashmap的capacity会一直是2的整数幂。

// 重新调整HashMap的大小,newCapacity是调整后的单位 
void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
        //旧容量不小于最大容量(一般不会发生,反正我没遇到过)
            threshold = Integer.MAX_VALUE;
            return;
        }
     //一般扩容
    // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中,  
    // 然后,将“新HashMap”赋值给“旧HashMap”。 
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

很明显,是新建了一个HashMap的底层数组,而后调用transfer方法,将就HashMap的全部元素添加到新的HashMap中(要重新计算元素在新的数组中的索引位置)。

transfer方法的源码如下:

// 将HashMap中的全部元素都添加到newTable中 
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);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

遍历原表table ,从table[0]开始,e=table[0],不为null就创建一个临时Entry next引用e.的下一个Entry,然后把e放到新表中,头插到table[i]中,i由indexFor方法决定i(h&newCapacity),然后让e=next,继续遍历拷贝。

扩容之后继续插入要插入的Entry,这个时候就要重新hash了,因为旧表已经扩容了,若果key为nul任然是0。

然后进行真正的插入,调用 createEntry(hash, key, value, bucketIndex),

下面是源码:

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
//进行头插,创建一个新的entry,
 Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

新的entry复制到table[bucketIndex],并next引用原来的table[bucketIndex],完成。

……..

仅仅只是HashMap的普通扩容,就这么麻烦,如果再加上线程安全,而加同步的话,那么效率可想而知.并且,HashMap在高并发场景下调用transfer方法,可能会出现环形链表,导致程序死循环。

原文  http://www.cnblogs.com/codingmode/p/12716413.html
正文到此结束
Loading...