java集合

集合

集合类存放于 Java.util 包中，主要有 3 种：set(集）、list(列表包含 Queue）和 map(映射)。

Collection：Collection 是集合 List、Set、Queue 的最基本的接口。
Iterator：迭代器，可以通过迭代器遍历集合中的数据
Map：是映射表的基础接口

list

ArrayList

排列有序，可重复

底层使用数组

查询速度快，增删慢，getter()和setter()方法快

线程不安全

当容量不够时，ArrayList是当前容量 * 1.5 + 1

Vector

排列有序，可重复

底层使用数组

查询速度快，增删慢

线程安全，效率低

当容量不够时，Vector默认扩展一倍容量

LinkedList

排列有序，可重复

底层使用双向循环链表数据结构

查询速度慢，增删快，add() 和 remove()方法快

线程不安全

Set

HashSet

排序无序，不可重复

底层使用Hash表实现

存取速度快

内部是HashMap

TreeSet

排序无序，不可重复

底层使用二叉树实现

排序存储

内部是TreeMap的SortedSet

LinkedHashSet

采用hash表存储，并用双向链表记录插入顺序

内部是LinkedHashMap

Queue

在两端出入的List,所以也可以用数组或链表来实现

Map

HashMap

键不可重复，值可重复

底层哈希表

线程不安全

允许Key值为null,value也可以为null

HashTable

键不可重复，值可重复

底层哈希表

线程安全

Key、value都不允许为null

TreeMap

键不可重复，值可重复

底层二叉树

HashMap源码分析

Jdk 7 使用头插法数据结构使用数组 + 链表

Jdk 8 使用尾插法数据结构使用数组 + 链表 + 红黑树

1
2
3

1. initialCapacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。 
2. loadFactor：负载因子，默认为 0.75。 
3. threshold：扩容的阈值，等于 capacity * 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);
}

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

把tableSizeFor 复制到你的类中，执行

static final int tableSizeFor(int cap) {
    int MAXIMUM_CAPACITY = 1 << 30;
    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;
}

发现这个方法会返回 1 2 4 8 16 32，结合注释，输入一个数，返回一个能包含输入数的2次方的一个数。

int 32位4个字节

>>>右移

最高位无论是0还是1都补0，空位补0

|按位或

两个位置上任一位置上是1，结果就是1，两个位置上都是0，结果才是0

// 走  n<0
System.out.println(tableSizeFor(0));
// 走 n + 1
System.out.println(tableSizeFor(1));
// 走 MAXIMUM_CAPACITY
System.out.println(tableSizeFor(1 << 30));
// 走 MAXIMUM_CAPACITY
System.out.println(tableSizeFor(Integer.MAX_VALUE));

输入一个非2的次方的数，如33

int n = cap - 1;
// n >>> 1 0010 0000----> 0001 0000  16   
// n =  32 | 16   0010 0000  ----> 0011 0000  48
n |= n >>> 1;
// n >>> 2 0011 0000 ----> 0000 1100  12   
// n =  48 | 12   0011 0000  ----> 0011 1100  60
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;

>>> 取高位的值 补 低位  如果 高位值没有了就为0了
| 是增大数
  
0000 0000		0
0000 0001		1
0000 0011		3
0000 0111		7
0000 1111		15
0001 1111		31
0011 1111   63
0111 1111		127

PUT方法

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

^按位异或

两个位置上值相同，结果就是0，两个位置上值不相同，结果才是1

当key == null 时 hash值为0；

当key不为空时，hash值为对象的hashcode 异或对象的hashcode的高16位。

hashMap的存储

节点定义

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

数组

1	`transient Node<K,V>[] table;`

节点定义中Node<K,V> next;表示为单向链表。

put方法

onlyIfAbsent 不存在时设置value

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
          	// 如果数组为空，调用扩容方法。
            n = (tab = resize()).length;
  					// 存储数组位置 由（数组长度-1）& hash(key)的值
        if ((p = tab[i = (n - 1) & hash]) == null)
          	// 如果数组位置上是空才放上
            tab[i] = newNode(hash, key, value, null);
        else {
          // 如果数组位置上不为空
            Node<K,V> e; K k;
          // 这一行就是对象为什么要重写hashCode()和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) {
                      // 如果数组索引位置上的节点的next为空，插入链表节点
                        p.next = newNode(hash, key, value, null);
                      // TREEIFY_THRESHOLD 树形阈值 默认 8   就是链表长度等于8时 转为红黑树插入。
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                          // 扩容(扩容后hash有可能就不一样了)  或  转成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                  	// 找到已经存在的节点
                    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;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
  			// 如果容量大于阈值，扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

& 按位与

两个位置上任一位置上是0，结果就是0，两个位置上都是1，结果才是1

1 2	`红黑树的put e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);`

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 {
          	// 把链表节点转为 树节点
            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);
    }
}

头插和尾插：

hashmap是线程非安全的，jdk1.7多线程情况下，会出现get()方法死循环，是因为扩容时会调整节点的位置，以前是数组的元素，现在变成链表中的一个元素，节点A与节点B,以前AB都是数组索引位置上，A的下一个节点指向B,别一个线程进行扩容后，B经过哈希函数算出位置在A之后，这时A的下一个节点指向B,B的下一个节点是A,这时就造成了死循环。

jdk1.7与1.8中hashmap的区别

1. 最重要的一点是底层结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构;
2. jdk1.7中当哈希表为空时，会先调用inflateTable()初始化一个数组；而1.8则是直接调用resize()扩容;
3. 插入键值对的put方法的区别，1.8中会将节点插入到链表尾部，而1.7中是采用头插；
4. jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值，而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀；
5. 扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前；
6. jdk1.8是扩容时通过hash&cap==0将链表分散，无需改变hash值，而1.7是通过更新hashSeed来修改hash值达到分散的目的；
7. 扩容策略：1.7中是只要不小于阈值就直接扩容2倍；而1.8的扩容策略会更优化，当数组容量未达到64时，以2倍进行扩容，超过64之后若桶中元素个数不小于7就将链表转换为红黑树，但如果红黑树中的元素个数小于6就会还原为链表，当红黑树中元素不小于32的时候才会再次扩容。

总结

获取hash值：

当key == null 时 hash值为0；

当key不为空时，hash值为对象的hashcode 异或对象的hashcode的高16位。

如果数组为空，调用扩容方法初始化。

算出存储数组位置由（数组长度-1）& hash值

如果数组位置上是空才放上

如果数组位置上不为空

数组上的节点就是要修改的节点，走后续的修改

如果数组上的节点是树节点，走树的查找或插入或修改

如果不是树节点，就循环，到最后一个节点插入

如果循环次数超过8位，走树化，如果数组容量不足64，走扩容，如果满足则把链表转为红黑树

如果是修改节点的value，则修改并返回。

如果容量大于阈值则扩容。

扩容(resize)方法

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) {
          	// 当老的容量大于  1 >> 30 时  
            if (oldCap >= MAXIMUM_CAPACITY) {
              	// 扩容阈值  =  int最大值  结束扩容
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }  // 当老的容量扩容 2 倍  小于  最大容量，并且 老的容量 大于 默认容量时 
          		// newCap = oldCap << 1  这个是个赋值操作，把新的容量扩容2倍
          		// 扩容阈值扩容2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
          	// 当扩容阈值大于0  新的容量 = 老的扩容阈值
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
          	// 0 容量 或 0扩容阈值  时使用默认值 初始化 16  0.75 * 16
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
  			// 上面未重新赋值新的扩容阈值
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
          	// 如果 新的容量  和  新的扩容阈值不超过最大容量，设置为 新容量 * 负载因子；
          	// 否则设置 Int最大值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
  			// 新数组
        @SuppressWarnings({"rawtypes","unchecked"})
        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) {
                    oldTab[j] = null;
                    if (e.next == null)
                      	// 节点无链表直接设置
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                      	// 树节点设置
                        ((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;
    }

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;
  			// 数组不为空，数组索引位置上的节点不为空
        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;
    }

java

#java

java集合

http://hanqichuan.com/2022/07/11/java/java集合/

作者

韩启川

发布于

2022年7月11日

许可协议

java并发编程上一篇

spring_boot_config实践下一篇