JDK7 HashMap源码解析

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: JDK7 HashMap源码解析

为什么HashMap中在链表与数组的选择时选择了数组?

因为使用链表的话访问查询会比较低(get方法),在ArrayList中可以直接使用下表来获取数据,但是链表需要一个位置一个位置遍历来查询。

在HashMap中get和put使用的频率都是非常的高的,所以我们也需要同时去保证他们的效率。

JDK 1.8 前 : 数组 + 链表


put方法:


● 通过 key 的 hashCode 经过 扰动函数(hash()) 处理过后得到 hash 值

● 通过 (n - 1) & hash (高效的求余数的办法,相当于)判断当前元素存放的位置(n 指的是数组的长度)

● 如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同

● 如果相同的话,直接覆盖,不相同就通过 拉链法 解决冲突

源码:


* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous(以前的) value associated with <tt>key</tt>, or
*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
*         (A <tt>null</tt> return can also indicate that the map
*         previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
     // 如果table={}
    if (table == EMPTY_TABLE) {
     //初始化
        inflateTable(threshold);
    }
//查看key是否位null
    if (key == null)
        return putForNullKey(value);
//对key求hash
    int hash = hash(key);
     //Returns index for hash code h.
    int i = indexFor(hash, table.length);
//从第i个位置的table开始  该节点是否位null(是否是最后一个节点,是退出循环)   
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
       //hash值是否相等,key是否相等。如果不相等先取到旧值,再覆盖,最后将久值返回
        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;
}


addEntry 方法


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


createEntry方法


void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
//新建一个节点,并把它放到table的前面
      //创建新节点 Entry(int h, K k, V v, Entry<K,V> n)//Creates new entry.
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
//  indexFor  根据hash值计算table中的i的大小
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

在put开头会先判断table={}是否成立,是则对hashmap进行初始化


The next size value at which to resize (capacity * load factor).
int threshold;
• 1
• 2


inflateTable方法


/**
 * Inflates the table.
 */
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}


roundUpToPowerOf2 方法


//找到一个大于或等于number的2的幂
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
        // number <=  1   , number = 1
      //    number > 1  时 :number是否是大于MAXIMUM_CAPACITY,如果大于MAXIMUM_CAPACITY那么容量就等于MAXIMUM_CAPACITY。如果小于那么就先number减1,然后翻倍在求翻倍后的小于等于参数的最大2的幂的值
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}


highestOneBit方法 (图解)


//获取小于等于参数的最大2的幂的值
public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}


扩容:


addEntry方法


/**
 * The number of key-value mappings contained in this map.
 */
transient int size;//这个映射中包含的键值映射的数量
/**
 * The next size value at which to resize (capacity * load factor).
 * @serial
 */
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated. 
int threshold;//要调整大小的下一个大小值(容量负载因子) 16 * 0.75
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);
}


resize方法


void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
     //new一个新对象 容量为newCapacity
    Entry[] newTable = new Entry[newCapacity];
//
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}


transfer方法


//Transfers all entries from current table to newTable.
void transfer(Entry[] newTable, boolean rehash) {
   int newCapacity = newTable.length;//新数组的容量
     // 遍历桶(table)
   for (Entry<K,V> e : table) {
       while(null != e) {
           Entry<K,V> next = e.next;
                      //rehash 
           if (rehash) {
                              //key 是否为空, 是 e.hash = 0 否 再hash
               e.hash = null == e.key ? 0 : hash(e.key);
           }
                     //算出新的数组下标
           int i = indexFor(e.hash, newCapacity);
                     //将当前的旧数组的下一个元素  指向 新数组中计算出来的对应元素中
           e.next = newTable[i];
             // 
           newTable[i] = e;
              //将next作为数组的头部
           e = next;
       }
   }
}


上面的扩容时,在单线程的时候是不会出问题的,但是在多线程的情况下,会出现死锁。


hash函数


final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    // 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);
}


使用的是头插法:因为如果是尾插法需要从头部依次遍历找打最后一个元素进行插入(最后一个节点next==null),这样就需要花费时间遍历。所以1.7使用的是头插法。


get方法:


public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}


getForNullKey方法


private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}


getEntry方法


//获取节点
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
  // key ==null 返回0,否则返回key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //计算楚下标,
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
//hash值相等并且key相等  那么e就是想找的节点
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}


注意: (n - 1) & hash 相当于 hash % n, (n - 1) & hash 是一种高效的求余数的办法。在默认容量16时,&操作只需要留下最后的4位,前面的都可以舍去。 因为比8更高位的都来自于8的2次幂,所以高位的1都是可以整除8,可以直接舍弃。(只有除数是2n才可以这样的操作)

0 0 0 0 0 0 0 0 0

256 128 64 32 16 8 4 2 1

直接&8的话是不行的,假设最后四位是1XXX,那么1XXX&1000=1000,很明显对8取余得到的结果不可能是8,余数应在0到除数减一之间,所以我们需要对&7,让取余结果最大在0-7之间。这就是为什么要&(2n-1)。

相关文章
|
1天前
|
缓存 Java 索引
查看并解析当前jdk的垃圾收集器
本文介绍了如何查看和解析当前JDK使用的垃圾收集器,通过在IDEA中配置JVM选项并运行示例代码来展示G1垃圾回收器的详细信息和命令行标志。
6 0
查看并解析当前jdk的垃圾收集器
|
2月前
|
算法 安全 Java
深入JDK源码:揭开ConcurrentHashMap底层结构的神秘面纱
【8月更文挑战第24天】`ConcurrentHashMap`是Java并发编程中不可或缺的线程安全哈希表实现。它通过精巧的锁机制和无锁算法显著提升了并发性能。本文首先介绍了早期版本中使用的“段”结构,每个段是一个带有独立锁的小型哈希表,能够减少线程间竞争并支持动态扩容以应对高并发场景。随后探讨了JDK 8的重大改进:取消段的概念,采用更细粒度的锁控制,并引入`Node`等内部类以及CAS操作,有效解决了哈希冲突并实现了高性能的并发访问。这些设计使得`ConcurrentHashMap`成为构建高效多线程应用的强大工具。
45 2
|
5月前
|
Java
IDEA debug HashMap源码的心得
IDEA debug HashMap源码的心得
47 0
|
2月前
|
存储 Java
【Java集合类面试七】、 JDK7和JDK8中的HashMap有什么区别?
JDK7中的HashMap使用数组加链表解决冲突,而JDK8增加了红黑树结构以优化链表过长时的性能,提高查找效率。
|
4月前
|
存储 安全 Java
深入解析Java HashMap的高性能扩容机制与树化优化
深入解析Java HashMap的高性能扩容机制与树化优化
131 1
|
4月前
|
存储 安全 Java
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
33 0
|
4月前
HashMap源码
HashMap源码
|
4月前
|
存储 算法 安全
JDK源码分析-HashMap
JDK源码分析-HashMap
|
4月前
|
Java Spring
深入解析Spring源码,揭示JDK动态代理的工作原理。
深入解析Spring源码,揭示JDK动态代理的工作原理。
51 0
|
5月前
|
Java 索引
【JAVA学习之路 | 进阶篇】HashMap源码剖析
【JAVA学习之路 | 进阶篇】HashMap源码剖析

推荐镜像

更多