review了一次HashMap

àì夳堔傛蜴生んèń 2022-12-05 01:40 137阅读 0赞

# 一、是什么 #

*  支持空值与空Key
 *  不支持高并发
 *  无序
 *  迭代器收集视图的时间取决于箱子的大小
 *  初始化容量，负载因子是哈希表的两个重要的属性
 *  判断key的时候取决hashCode函数
 *  使之变同步的方式Collections.synchronizedMap(new HashMap(…));
 *  支持fail-fast机制，保证不能被多个线程修改，通过modCount这个字段实现，判断这个字段是否被修改
 *  过大会转为红黑树，算法复杂度降为O(log n)，红黑排序是根据key的hash大小
 *  判断key是否相等的方法一定是hashCode相等，跟equals相等。
 *  如果key的hashCode相等，equals不等，在有Comparable的情况下，用该接口比较前后关系，速度快，此时如果相等也会跟后面逻辑一致。如果没有实现这个接口的话，就要会通过调用 tieBreakOrder(Object a,Object b) 方法来对它们进行比较。这个方法首先会比较两个键对象的类名，如果相等再调用 System.identityHashCode 方法进行比较，很耗时。
 *  \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MMxhrDvW-1599568140413)(H:\\我的知识库\\知识库\\源码笔记\\image\\HashMap.putVal()\].key相等时的处理.png)
 *  树化的时候，会通过Node.next保持着原来链表的相对关系，让迭代器容易访问

# 二、字段 #

## 1、默认容量16 ##

/** * The default initial capacity - MUST be a power of two. */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量

/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
        static final int MAXIMUM_CAPACITY = 1 << 30;

## 2、默认负载因子0.75 ##

/** * The load factor used when none specified in constructor. */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

## 3、树化阀8、拉直阀6、最小树化容量64 ##

/** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */
        static final int TREEIFY_THRESHOLD = 8;
    
        /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */
        static final int MIN_TREEIFY_CAPACITY = 64;

4、树节点与普通节点

/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */
        static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            V value;
            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;
            }
    
            public final K getKey()        {  return key; }
            public final V getValue()      {  return value; }
            public final String toString() {  return key + "=" + value; }
    
            public final int hashCode() { 
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) { 
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) { 
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) { 
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }
    
        /** * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. */
        static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
        	...
        }

## 4、其他属性跟ConcurrentHashMap一样就没啥好写的 ##

## 三、方法 ##

只写有知识点的方法

## 1、构造函数，无论你传什么容量都会变成二的次方 ##

## 2、size() ##

相比ConcurrentHashMap就很简单了，直接记录在size一个字段里面。

## 3、get() ##

判断是否是第一个元素，是的话直接返回，不是的话，判断是链表还是红黑树。链表递归查找，红黑树就O（log n）了

## 4、put() ##

找到元素插入位置并插入（检查是否树化），修改modCount（为了fast\_fail），检查是否扩容

## 5、treeifyBin() ##

树化函数，如果判断整个表格还没达到树化标准的话，那么先扩容，然后再对拉链做树化。