logo头像
ICQL

215_javase-map

Map<K,V>接口

Map API

  • 偶对象保存的最大父接口
  • TreeMap是基于树的实现,HashMap,HashTable,ConcurrentHashMap是基于hash表的实现。HashTable和HashMap在代码实现上,基本上是一样的,一个是线程安全的,一个非线程安全。ConcurrentHashMap也是线程安全的,但性能比HashTable好很多,HashTable是锁整个Map对象,而ConcurrentHashMap是锁Map的部分结构,LinkedHashMap继承HashMap

HashMap原理

  • 构造函数和基础字段
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public HashMap() {
    //DEFAULT_LOAD_FACTOR = 0.75f;默认负载因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    transient Node<K,V>[] table;//底层数组
    //static class Node<K,V> implements Map.Entry<K,V>{}
    //Node<K,V>是一个静态内部类,是单链表的结点类
    //实现了Map.Entry<K,V>
    transient int size;//逻辑长度
    transient int modCount;//修改次数
    final float loadFactor;//负载因子
    int threshold;
    transient Set<Map.Entry<K,V>> entrySet;
  • 分析代码
    1
    2
    3
    4
    Map<String,String> map = new HashMap<>();
    map.put("test1","test1");
    map.put("test2","test2");
    map.put("test1","test1111");
  • 执行构造函数:只初始化了负载因子为0.75,其他字段均为null
  • 调用put方法插入数据
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    //put方法,调用hash方法和putVal方法
    public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    }
    //
    //
    //hash方法:又叫扰动函数
    //1、key.hashCode(),调用key的hashCode()方法得到key的哈希值
    //2、复习3个位运算符
    // &与运算:两个数相应位均为1结果为1,其他均为0
    // |或运算:两个数相应位都为0结果为0,其他均为1
    // ^异或运算:两个数相应位相同则为0,不同则为1
    //3、key的哈希值是int32位的值,将哈希值右移16位得到(16个0+原哈希值高16位),
    // 再将(16个0+原哈希值高16位)和原哈希值做异或运算,
    // 相当于原哈希值的高16位和16个0、低16位和高16位做异或运算,以此来加大hash值低位的随机性
    //4、为什么要加大hash值低位的随机性?
    // 主要是因为防止key的散列函数本身做得不好,分布上成等差数列等漏洞,恰好使最后几个低位呈现规律性重复,
    // 而HashMap的数组长度全部取2的整次幂,这样(数组长度-1)正好相当于一个“低位掩码”,
    // “与”操作的结果就是散列值的高位全部归零,只保留低位值,用来做HashMap数组下标(不会出现超出数组索引的情况),
    // 如果hash值的后几位重复太多就会造成数据存放在HashMap数组不够随机均匀
    //
    //5、示例,HashMap数组第一次的初始容量为 n = 1<<4 = 16
    // h = hashCode() :1010 1101 1111 1011 1111 1101 1000 1111
    // h >>> 16 :0000 0000 0000 0000 1010 1101 1111 1011
    // hash=h^(h>>>>16) :0101 0010 1111 1011 0101 0000 0111 0100
    // n-1 = 16-1 = 15 :0000 0000 0000 0000 0000 0000 0000 1111
    // hash & (n-1) :0000 0000 0000 0000 0000 0000 0000 0100
    // 数组下标为 0100 = 4
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //
    //
    //putVal方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //HashMap数组为空或者其长度为0时,即构造函数执行后第一次put数据时
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;//resize方法进行数组扩容
    //数组中的计算出的索引的位置还没有数据,即第一次往这个位置放数据
    //第一次放,所以直接放在这个位置
    //(n - 1) & hash就是上述的取数组下标操作
    if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);//newNode方法构造一个Node结点
    //数组的这个索引位置已经有数据了
    else {
    Node<K,V> e; K k;
    //新放入的数据是这个位置的头结点
    //条件:头结点的hash和新放入数据的hash相同 并且 (key的引用地址相同 或者 equals判断相同)
    if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
    //新放入的数据是红黑树的其他结点
    else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//插入数组这个位置的红黑树
    //新放入的数据是单链表的其他结点
    else {
    for (int binCount = 0; ; ++binCount) {
    //循环找到单链表或红黑树的最后一个结点
    if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);//构造新数据结点
    if (binCount >= TREEIFY_THRESHOLD - 1) //TREEIFY_THRESHOLD值为8,即单链表长度>=8时
    treeifyBin(tab, hash);//把单链表转化为红黑树
    break;//跳出循环
    }
    //如果在单链表或红黑树中找到要插入的数据
    //条件:头结点的hash和新放入数据的hash相同 并且 (key的引用地址相同 或者 equals判断相同)
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    break;//跳出循环
    p = e;
    }
    }
    //上面找到了 新插入数据 为已存在的数据,将只更新value
    if (e != null) {
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
    e.value = value;
    afterNodeAccess(e);
    return oldValue;
    }
    }
    ++modCount;
    //如果当前的数据个数(逻辑长度) 超过 (负载因子 * 数组长度),执行数组扩容
    if (++size > threshold)
    resize();
    afterNodeInsertion(evict);
    return null;
    }
    //
    //
    //扩容方法:将原来的容量 扩容 到2倍


    //线程不安全体现:
    //1)put会丢失更新,假如两个线程得到的数组index一样,都准备往这个index上的链表插入数据,得到的链表头节点一样,线程A先插入,而后停止线程B再插入就会造成A的数据丢失
    //2)扩容resize容易引起 环形链表

    final Node<K,V>[] resize(){}

LinkedHashMap原理

  • 继承HashMap,LinkedHashMap比HashMap多了一个双向链表的维护

ConcurrentHashMap原理

HashTable原理

TreeMap原理

参考

微信打赏

赞赏是不耍流氓的鼓励