转载

HashMap浅阅读

// HashMap默认初始化长度,默认值为16,必须为2的幂次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大长度,如果任意一个带有参数的构造函数隐式指定时使用的最大容量。 必须是两个<= 1 << 30的幂。
static final int MAXIMUM_CAPACITY = 1 << 30;
// 在构造函数中未指定时使用的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 是否转换成红黑树的链表长度的阀值
static final int TREEIFY_THRESHOLD = 8;
// 取消树化的阀值
static final int UNTREEIFY_THRESHOLD = 6;
// 进行树化时,数组的最小长度阀值
static final int MIN_TREEIFY_CAPACITY = 64;
// 该表在首次使用时初始化,并根据需要调整大小。分配后,长度始终是2的幂。
transient Node<K,V>[] table;
// 保存缓存的entrySet()。请注意,* KeySet()和values()使用AbstractMap字段
transient Set<Map.Entry<K,V>> entrySet;
// 长度
transient int size;
// 对该HashMap进行结构修改的次数*结构修改是指更改HashMap中的映射次数或以其他方式修改其内部结构(例如,重新哈希)的次数。
transient int modCount;
// 下一个要调整大小的大小值(容量*负载系数)(capacity * loadFactor) 数组扩容的阀值
int threshold;
// 负载因子
final float loadFactor;
复制代码

HashMap的初始化方式

// 空参
public HashMap();

// 指定初始化长度
public HashMap(int initialCapacity);

// 指定初始化长度和负载因子
public HashMap(int initialCapacity, float loadFactor);

// 构造一个新的HashMap
public HashMap(Map<? extends K, ? extends V> m);
复制代码

指定初始化长度

/**
 * @param initialCapacity 	初始化长度
 */
public HashMap(int initialCapacity){
    this.HashMap(initialCapacity,loadFactor)
}
/**
 * @param initialCapacity 	初始化长度
 * @param loadFactor 		负载因子
 */
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);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
复制代码

指定初始化长度时,会使用默认负载因子,调用指定初始化长度和默认的负载因子的构造函数。

在HashMap(int initialCapacity, float loadFactor)中,调用 tableSizeFor(int cap) 计算要调整容器的大小

/**
 * @param cap 	初始化长度
 * @return 对于给定的目标容量,返回两倍大小的幂。
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码

对初始化长度,进行移位和按位或运算(运算规则:0|0=0; 0|1=1; 1|0=1; 1|1=1);

**例如:**初始化长度为5;

HashMap浅阅读

Put 方法

/**
 * 将指定的键与值进行关联
 * @param key 	键
 * @param value 值
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
/**
 * 计算hash值
 * 计算key.hashCode() 并将散列*的较高位扩展(XOR)到较低位
 * 因为该表使用2的幂次掩码,所以仅在当前掩码上方的位中发生变化的哈希集将总是冲突
 * @param key 	计算hash值得对象 
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
 * @param hash 			hash值
 * @param key     		关键的键
 * @param value  		关联的值 
 * @param onlyIfAbsent	如果为true,请不要更改现有值
 * @param evict  		如果为false,则表处于创建模式
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    // 节点数组集合
    Node<K,V>[] tab; 
    // 节点 hash值、键值对和下一个节点的指针,参见下方Node节点的结构
    // 保存的是传入的key通过hash值计算出的索引,在节点数组中对应的节点
    Node<K,V> p;
    int n, i;
    // 判断此时的数组是否为null,实际HashMap初始化值是在第一次添加值得时候
    // 若为null或者长度为0,则调用resize()方法进行初始化数组空间,参见下方resize()方法
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 使用取地址法,计算当前键在数组中的索引位置
    // 将当前索引位置的节点赋值给 p 节点
    // 若当前节点为空,则创建一个新的节点,添加到指定索引位置的节点数组中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //指定索引位置不为空时,则产生hash冲突,此时以链表的形式存储
        // e 为通过取地址法计算出当前hash值对应的节点数组中的节点
        Node<K,V> e;
        K k;
        // p.hash == hash 判断指定索引位置的p节点的hash值与传入的hash值是否相同;
        // (k = p.key) == key 判断指定索引位置的p节点的键与传入的键key的地址是否相同
        // key != null && key.equals(k) 判断键不为空并且指定索引位置的p节点的key的值是否相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 传入的key在数组中已经存在,属于重复的键,对应的值会进行覆盖操作
            e = p;
        else if (p instanceof TreeNode)
            // 当前指定索引位置的节点为红黑树节点,添加树节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 属于产生了hash冲突,但是还未树化的链表
            // 执行死循环,查找该索引位置的链表中的尾结点
            for (int binCount = 0; ; ++binCount) {
                // 若当前节点数组中的p节点的下一个节点为null
                if ((e = p.next) == null) {
                    // 新建一个节点,添加到 p 节点后面
                    p.next = newNode(hash, key, value, null);
                    // 当前尾结点的长度是否达到树化的阀值
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 达到树化阀值,判断是否满足将链表树化为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // e.hash == hash 判断链表中的节点的hash值与传入键值对的hash值
                // (k = e.key) == key 比较链表中的key 与传入的key地址
                // key != null && key.equals(k)) 比较传入的key与链表中的key
                // 应该不会执行下面的if代码,相同链表中的hash值应该是一致的
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent为false,则表处于创建模式
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 当前数组长度+1 大于扩容的阀值,进行数组扩容
    if (++size > threshold)
        // 扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}
复制代码

treeifyBin() 方法:

/**
 * 判断是否达到将链表树化为红黑树并且树化操作的条件
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 数组为空,或者数组长度小于64时,不树化,只进行数组扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 链表转换为红黑树操作
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 创建新节点,next域为null
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}
复制代码

newNode()方法:

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}
复制代码

Node结构:

/**
 * 自定义节点内部类
 */
static class Node<K,V> implements Map.Entry<K,V> {
    // 当前节点key 的 hash值
    final int hash;
    // 键
    final K key;
    // 值
    V value;
    // 指向下一个节点的指针
    // 在产生hash冲突时,会以链表的形式存储,此属性指向当前节点的下一个节点
    Node<K,V> next;
	// 构造方法
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    //... 省略了Node节点中的一些方法
}
复制代码

resize()方法:

/**
 * 数组的初始化、扩容方法
 * @return 节点数组对象
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // 判断数组是否为空(是否初始化)
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 老的数组长度的扩容阀值
    int oldThr = threshold;
    // 新数组初始化长度和扩容阀值
    int newCap, newThr = 0;
    // 数组已经初始化,此时执行扩容操作
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 数组长度小于最大长度
        // 数组长度扩大2倍 newCap = oldCap << 1 (newCap = oldCap * 2)的值小于最大长度
        // 老数组长度大于默认初始化长度
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新的数组长度的扩容阀值扩大 2倍 newThr = oldThr << 1 (newThr = oldThr * 1)
            newThr = oldThr << 1; // double threshold
    }
    // 数组还未初始化,调用了指定初始化长度的构造函数, 扩容阀值大于 0
    // oldThr 长度是 在初始化构造函数中,通过tableSizeFor(cap)方法计算
    else if (oldThr > 0) // initial capacity was placed in threshold
       	// 数组的长度为 老数组的扩容阀值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 数组还未初始化,通过空参构造方法初始化
        // 默认长度与默认的数组扩容阀值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 若新数组的扩容的阀值为 0,则通过计算公式计算长度
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    // 将新数组的扩容阀值 赋值给成员变量
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 初始化一个长度为newCap的节点数组,赋值给成员变量table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 数组扩容操作,老数组不为空
    if (oldTab != null) {
        // 遍历数组集合
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 取出节点数组中对应索引位置的节点,并且将老节点数组中对应索引位置的节点置为null
                oldTab[j] = null;
                if (e.next == null)
                    // 取出节点为当前链表的尾结点
                    // 根据当前节点的hash值与新数组长度,重新计算索引位置,存放当前节点数据
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 取出节点为红黑树的树节点,参见下面的split()方法
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            // 数组或链表中  低位节点
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // 数组或链表中  高位节点
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        // 将低位节点直接存储到数组中对应的索引位置
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        //将高位节点存储到扩容后的数组中对应的索引位置
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
复制代码

TreeNode 红黑树节点

Field 属性:

// 父节点
TreeNode<K,V> parent;  // red-black tree links
// 左叶子节点
TreeNode<K,V> left;
// 右叶子节点
TreeNode<K,V> right;
// 前一个节点
TreeNode<K,V> prev;    // needed to unlink next upon deletion (删除后需要取消链接)
// 是否是红节点
boolean red;
复制代码

split() 方法:

/**
 * 将树箱中的节点拆分为上部树箱和下部树箱,如果现在太小,则或取消树化;仅从调整大小调用。
 * @param map 		HashMap集合
 * @param tab 		新的节点数组
 * @param index 	被拆分表的索引
 * @param bit 		老的数组的长度
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            // 低位节点 
            // 尾插法
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            // 低位节点数
            ++lc;
        }
        else {
            // 高位节点
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            // 高位节点数
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            // 除树化,链表节点小于等于6时,红黑树转换成链表
            tab[index] = loHead.untreeify(map);
        else {
            // 树节点转存到新的数组中指定的索引位置
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified) 否则,已经存在树
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            // 除树化,链表节点小于等于6时,红黑树转换成链表
            tab[index + bit] = hiHead.untreeify(map);
        else {
            // 树节点转存到新的数组中指定的索引位置
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}
复制代码

putTreeVal() 添加节点方法

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        // 判断是左节点还是右节点
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // 当前添加节点为根节点 p 节点
            return p;
        	//	comparableClassFor 判断是否实现了Comparable<C>接口
        	//	实现了Comparable<C>接口,则返回当前类型,否则返回 null
        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                 // 判断pk是否为空		 |   => pk == null => 0  或者
                 //	判断pk是否是kc的类型 	|	=> pk.getClass() != kc  => 0
                 // 比较 k 与 x 是否相同	 否则 => ((Comparable)k).compareTo(pk))
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                // p节点左子树不为null,则搜索左子树
                if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) ||
                    // p 节点右子树不为 null, 则搜索右子树
                    ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null))
                    // 将已存在的节点返回
                    return q;
            }
            // 用于在hashCodes相等且不可比较时对插入进行排序
            dir = tieBreakOrder(k, pk);
        }
		// 向红黑树中添加节点
        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 调整树结构
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}
复制代码

Get 方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;
    Node<K,V> first, e; 
    int n; K k;
    // 数组不为空
    // 数组长度大于0
    // 当前键对应 数组中 的索引位置上的节点不为null
    if ((tab = table) != null && 
        (n = tab.length) > 0 && 
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 查找键为首节点(当前键在数组中的节点)
            return first;
        // 查找链表或者红黑树
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                // 节点为树节点,获取树节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 遍历链表查找对应的节点
                if (e.hash == hash &&((k = e.key) == key || 
                                      (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
复制代码

注意:

  1. JDK1.8 中HashMap的实现:数组+(链表|红黑树)

  2. HashMap的初始化:在第一次put数据时,初始化

  3. HashMap中,指定了初始化长度,系统会默认设置为 (当前长度 <= 初始化长度为2的幂次方最小值)。例如: initialCapacity = 6 ,实际初始的长度为: 8

  4. HashMap的默认长度为16,默认负载因子为0.75f,默认扩容阀值为12

  5. HashMap 在链表转换成红黑树时,会首先判断数组的长度,大于64(MIN_TREEIFY_CAPACITY 最小树容量)时,才会进行树化,否则进行扩容

原文  https://juejin.im/post/5e0085ece51d455846232470
正文到此结束
Loading...