java集合框架初步理解

爱被打了一巴掌 2022-04-24 02:58 180阅读 0赞

前言:这是在慕课网上学习剑指Java面试-Offer直通车时所做的笔记,主要供本人复习之用.

**目录**

第一章  Collection

第二章 集合之List和Set

2.1 ArrayList

2.2 Vector

2.3 LinkedList

2.4 HashSet

2.5 TreeSet

2.5.1 自然排序

2.5.2 客户化排序

第三章 集合之map

3.1 HashMap

3.1.1 HashMap构造函数

3.1.2 HashMap Put方法

3.1.3 HashMap Get方法

3.1.4  hash运算

3.1.5  HashMap扩容

3.1.6 让HashMap变得线程安全

3.2 HashTable

3.3 ConccurentHashMap

3.3.1 早期的ConccurentHashMap

3.3.2 java8后的ConccurentHashMap

3.3.3 ConccurentHashMap的源码介绍

3.3.4 ConccurentHashMap put方法总结

3.4 HashMap,Hashtable,ConccurentHashMap的区别

--------------------

# 第一章  Collection #

集合作为一个容器可以存储多个元素,但是由于数据结构的不同java提供了多种集合类,将集合类中共性的功能不断向上抽取,最终形成了集合体系结构,可以看到除了Map体系以外,Collection接口是所有集合的根,Collection才是正统的狭义上的集合.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70][]

# 第二章 集合之List和Set #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 1][]

小例子:

public class DuplicateAndOrderTest {
        public static void main(String[] args) {
            LinkedList linkedList = new LinkedList();
            linkedList.add("111");
            linkedList.add("333");
            linkedList.add("222");
            linkedList.add("444");
            linkedList.add("555");
            linkedList.add("111");
            linkedList.get(1);
            System.out.println(linkedList);
            TreeSet treeSet = new TreeSet();
            treeSet.add("111");
            treeSet.add("333");
            treeSet.add("222");
            treeSet.add("444");
            treeSet.add("555");
            treeSet.add("111");
    
            System.out.println(treeSet);
        }
    
    }

输出为如下,所以TreeSet不支持重复,插入的值有序,LinkList支持重复,插入的值无序.

[111, 333, 222, 444, 555, 111]
    [111, 222, 333, 444, 555]

## 2.1 ArrayList ##

打开ArrayList源码,发现其确实是用数组实现的.elemetData就是它的数组.

transient Object[] elementData; // non-private to simplify nested class access

创建ArrayList时,就是去new出一个新的数组来.

public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

集合对于数组来讲,是可扩容的,即便对于数组实现的ArrayList来说也是可以扩容的.ArrayList的扩容就是创建一个新的数组,赋予新的长度,然后在覆盖掉原先的数组.进而实现所谓的动态扩容.

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

可以看到ArrayList并不是线程安全的.原因是其方法里既没有用到锁,也没有用到相关的CAS的技术.

public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

## 2.2 Vector ##

Vector也是通过数组实现的,可以看其构造函数.new的时候也是最终创建elementData这个数组.

public Vector(int initialCapacity, int capacityIncrement) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
            this.capacityIncrement = capacityIncrement;
        }

Vector是java早期提供线程安全的动态数组,可以看到其对外的public方法几乎都加上了synchronized同步锁.这表明这些方法都需要串行执行的,也就是说Vector不适用于高并发且对Vector有较高性能要求的场景.当然为了保证高并发又能线程安全本身就是一个比较矛盾的行为.Vector现在已经很少用了.

public synchronized void copyInto(Object[] anArray){//省略...}
    public synchronized void trimToSize() {//省略...}
    public synchronized void ensureCapacity(int minCapacity) {//省略...}

## 2.3 LinkedList ##

看代码可以知道LinkedList是通过链表来实现的.

transient Node<E> first;
    
    transient Node<E> last;

由于同样没有用到锁,也没有用到CAS,也就证明其和ArrayList一样,是线程不安全的,

## 2.4 HashSet ##

通过HashSet的源码可以知道,HashSet的底层其实是HashMap,在我们调用add方法的时候呢,其实是把元素以键的形式放入到hashmap中去了,同时对应上一个PRESENT的值,可以看到PRESENT是final的new object,既然hashset是hashmap的马甲,就留到后面讲解hashmap的时候再讲.

private static final Object PRESENT = new Object();
    
    private transient HashMap<E,Object> map;
    
    public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }

## 2.5 TreeSet ##

TreeSet的核心在于排序,在不关心排序的去重场景下,使用HashSet将获得更高的性能.如果关心排序才考虑使用TreeSet,TreeSet最典型的是使用了两种排序方式.

即基于元素对象自身实现的comparable接口自然排序,以及基于更为灵活不与单元元素绑定comparator接口的排序.

TreeSet其实是NavigableMap的马甲,因此TreeSet与HashSet雷同,都是通过add的形式将元素以键的形式保存到TreeMap的key中.而值就是final的new Object.

private transient NavigableMap<E,Object> m;
    
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
            return m.put(e, PRESENT)==null;
        }

NavigableMap是一个interface,由TreeMap实现,也就是说TreeSet是TreeMap的马甲.

public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    {
    
    }

当客户化排序comparator存在时,会返回使用客户化结果.用到了cpr的compare方法,也就是我们自己要实现的compare方法.

当客户化排序为空时,会调用自然排序是调用while里的逻辑,while里面主要调用了我们的key,也就是传入元素的ComparaTo方法进行排序.进而决定取出左边的元素还是右边的元素.也就是说这里是经过排序的,排序本身就来源与key里的compareTo方法.

final Entry<K,V> getEntry(Object key) {
            // Offload comparator-based version for sake of performance
            if (comparator != null)
                return getEntryUsingComparator(key);
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = k.compareTo(p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
            return null;
        }
    
    final Entry<K,V> getEntryUsingComparator(Object key) {
            @SuppressWarnings("unchecked")
                K k = (K) key;
            Comparator<? super K> cpr = comparator;
            if (cpr != null) {
                Entry<K,V> p = root;
                while (p != null) {
                    int cmp = cpr.compare(k, p.key);
                    if (cmp < 0)
                        p = p.left;
                    else if (cmp > 0)
                        p = p.right;
                    else
                        return p;
                }
            }
            return null;
        }

### **2.5.1 自然排序** ###

Customer类实现了Comparable接口,这就要求Cutomer类要实现euqals,compareTo,以及hashcode三个方法,同时为了确保Customer添加进TreeSet之后能正确的排序要求:

compareTo与equals方法需要按照相同的规则来比较两个对象是否相等.也就是说如果customer1 equals customer2为true,那么customer1 compareTo customer2为0,因为compareTo大于0表示customer1大于customer2,反之小于,等于0两者相等.

同时一旦重写了equals方法就要重写hashcode方法.即两个对象equals相等后,两个对象的hashcode也应该相等.

总的来说,当对象实现了上述三个方法后就能传入treeset进行排序了.

public class Customer implements Comparable{
        private String name;
    
        private int age;
    
        public Customer(String name, int age) {
            this.age = age;
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (!(obj instanceof Customer))
                return false;
            final Customer other = (Customer) obj;
    
            if (this.name.equals(other.getName()) && this.age == other.getAge())
                return true;
            else
                return false;
        }
        @Override
        public int compareTo(Object o) {
            Customer other = (Customer) o;
    
            // 先按照name属性排序
            if (this.name.compareTo(other.getName()) > 0)
                return 1;
            if (this.name.compareTo(other.getName()) < 0)
                return -1;
    
            // 在按照age属性排序
            if (this.age > other.getAge())
                return 1;
            if (this.age < other.getAge())
                return -1;
            return 0;
    
        }
    
        @Override
        public int hashCode() {
            int result;
            result = (name == null ? 0 : name.hashCode());
            result = 29 * result + age;
            return result;
        }
        public static void main(String[] args) {
            Set<Customer> set = new TreeSet<Customer>();
            Customer customer1 = new Customer("Tom", 16);
            Customer customer2 = new Customer("Tom", 15);
            set.add(customer1);
            set.add(customer2);
            for(Customer c : set){
                System.out.println(c.name + " " + c.age);
            }
        }
    }

输出:

Tom 15  
Tom 16

可以看到经过了排序.

### 2.5.2 客户化排序 ###

我们不需要在customer中改变它的方法,只需要在外部类中实现Comparator接口,然后实现其中的compare方法即可,在compare中只对name进行排序.

public class CustomerComparator implements Comparator<Customer> {
        @Override
        public int compare(Customer c1, Customer c2) {
            if(c1.getName().compareTo(c2.getName())>0)return -1;
            if(c1.getName().compareTo(c2.getName())<0)return 1;
            return 0;
        }
    
        public static void main(String args[]){
            Set<Customer> set = new TreeSet<Customer>(new CustomerComparator());
    
            Customer customer1= new Customer("Tom",5);
            Customer customer2= new Customer("Tom",9);
            Customer customer3= new Customer("Tom",2);
            set.add(customer1);
            set.add(customer2);
            set.add(customer3);
            Iterator<Customer> it = set.iterator();
            while(it.hasNext()){
                Customer customer = it.next();
                System.out.println(customer.getName()+" "+customer.getAge());
            }
        }
    }

现在Customer既实现了Comparable同时在外部也实现了Comparator,执行的结果以Comparator为主.

输出:Tom 5

compare方法认为只要名字是相同的,那么它就是相同的东西,而我们的set是不支持存储重复的值的,因此只有一个能被留下,其它都被去重了.

也就是说在客户化排序与自然排序都存在的情况下,是以客户化排序优先的.

# 第三章 集合之map #

相对保存单列值的map与set来讲,map用于保存具有映射关系的数据,map保存的数据都是key value对的,也就是由key和value组成的键值对,map里的key是不可重复的,key用于标识集合里的每项数据,而value是可以重复的.可以看到key是由set组织起来的,value是由collection组织起来的.

Set<K> keySet();
    
    Collection<V> values();

map的整体结构如图1所示,其中HashTable比较特别,类似vector等早期集合,扩展自Dictionary.构造与HashMap有明显的不同,HashMap是Map的正统,大部分使用Map的场合就是放入,访问或者删除,而对于顺序没有什么特别的要求,HashMap在此种情况下就是最好的选择.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 2][] 图1

## 3.1 HashMap ##

HashMap(Java8以前):数组+链表,将key存在数组中,通过hash(key.hashCode())%len操作获得要添加的元素要存放的数组的位置,HashMap的hash算法实际上是通过位运算来进行的,相比取模效率更高,这里会有比较极端的情况,如果添加到hash表中不同的值的键位通过hash散列运算总是得出相同的值,这样会使某个位置的链表很长,链表查询需要从头部逐个遍历,因此最坏的情况下会从O(1)变成O(n)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 3][]

所以在java 8以后会使用一个常量TREEIFY\_THRESHOLD来控制是否将链表转换为红黑树,这意味着我们会将最坏的情况下性从O(n)提高到O(logn).

HashMap的内部结构:

hashmap可以看作是由数组table和链表来组成的复合结构.在java8以前数组的元素叫做entry,java8之后变成了node,因为引入了树,而无论是树或者链表里面的元素都是节点,因此声明为node比较贴切.

node是由键值对,哈希值,和指向的下一个节点组成的,而数组被分为一个个的bucket,通过哈希值决定了键值对在数组中的地址,哈希值相同的键值对则以链表的形式来存储,而链表的大小如果超过TREEIFY\_THRESHOLD,就会被改造成红黑树,当链表的大小低于UNTREEIFY\_THRESHOLD时,红黑树又将变成一个链表.

static final int TREEIFY_THRESHOLD = 8;
    
    static final int UNTREEIFY_THRESHOLD = 6;
    
    transient Node<K,V>[] table;
    
    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;
            }
        }

### 3.1.1 HashMap构造函数 ###

注:阅读代码的时候不要立刻陷入到细节中,要大体上先过一下,看它要做啥.

从构造函数来看,我们之前看到的table数组并没有在最初的时候就初始化好,而是仅仅给一些成员变量赋上了初始的值,所以我们有理由推断HashMap是按照lazyload的原则在首次使用的时候才会被初始化,这与hibernate的延迟加载原理十分相同,

public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

### 3.1.2 HashMap Put方法  ###

那我们来看一下它是如何使用的.在put调用时,如果table为空的话,它就会调用resize的方法来初始化table,同时当我们的size大于threshold时也会调用resize,所以resize既具备初始化,也具备扩容的方法.

然后会通过tab去做哈希运算,tab\[i = (n - 1) & hash\],hash是通过与或所产生的.

当hash过后的位置没有节点时,就会去新建一个节点.否则会去走else里的条件.

在else中如果发现同样的位置已经存在键值对,且键和传入进来的键值对是一样的,则直接替换数组里的元素,将在最后e!=null的方法体中完成替换,否则接着走下面的判断,判断当前的节点是否是已经树化了的节点,如果是树化了,则尝试去建立键值对,如果不是树化的,则进入else里面,按照链表的方式向链表中插入元素,同时判断链表的总数,一旦超过TREEIFY\_THRESHOLD则将链表进行树化.

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    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;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                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) // -1 for 1st
                                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;
        }
    static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

总结:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 4][]

### 3.1.3 HashMap Get方法 ###

主要是使用键对象的hashcode通过hash算法找到bucket的位置,找到bucket位置后就会调用key.equals方法找到链表中正确的节点,最终找到要找到的值返回.

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

### 3.1.4  hash运算 ###

除了树化可以提升性能,hash运算也是提升性能的关键,即将key映射到table中的运算.减少碰撞的方法有:

扰动函数:促使元素位置均匀,减少碰撞机率.

使用final对象且采用合适的equals和hashCode方法.使用String,Integer作为key是很好的选择因为这些包装类已经封装了equals和hashCode方法且是final的

在HashMap中hash的实现

static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    
        tab[i = (n - 1) & hash]；

即先获取hashCode再将高位移位到低位16位,也就是去除了16位的低位后再与原先的数据进行异或运算.

为什么不直接使用hashCode的值?因为hashcode返回的是int的散列值,如果拿散列值为下标去访问hashMap数组,考虑到int的范围有40亿,内存是放不下40亿长度的数组的,况且在扩容前的hashmap大小才16,直接拿散列值来用是不现实的.于是我们将高位向低位移动16位后再与自己做异或,这样混合原始码的高位和低位加大随机性,而且混合后的低位参砸了高位的特征,高位也被变相的保存了下来.

最后所以我们将hash值对数组n取余,得出元素在数组中的位置.

因为X % length = X & (length - 1),length为2的倍数,详解**:**[https://www.cnblogs.com/ysocean/p/9054804.html][https_www.cnblogs.com_ysocean_p_9054804.html]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 5][]

通过HashMap的构造函数,我们看到我们可以传入HashMap的初始值的大小,但是并不是传入的初始值是多大,实际上就是多大,而是经过tableSizeFor转变后的大小.tableSizeFor是要将其转换为其最接近的tableSize的值.这样主要是为了上面与hash值来进行取模.

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

### 3.1.5  HashMap扩容 ###

resize就是重新计算容量,向HashMap中不停的添加各种元素,到HashMap中无法装载更多元素时,对象就要扩大数组的长度,java里的数组是无法自动扩容的,方法是使用一个比较大的数组来代替一个比较小的数组,HashMap的负载因子,因为jdk默认的负载因子是比较符合场景需求的,当HashMap填满了百分之75的时候,将回去创建原来大小两倍的数组来重新调整map的大小.并将原来的对象放到新的bucket数组中.这个过程叫做rehash,因为它通过hash找到bucket的位置.

扩容的问题:

多线程环境下,调整大小会存在条件竞争,容易造成死锁.如果两个线程都发现hashmap需要重新调整大小了,它们就会同时试着调整大小,而如果条件竞争发生了,就会发生死锁.

同时因为要将原先的HashMap中的键值对重新移动到新的HashMap中去,这也是非常耗时的过程.

static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    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;
                }
                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
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                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;
        }

### 3.1.6 让HashMap变得线程安全 ###

调用synchronizedMap方法传入HashMap实例即可以将HashMap变得线程安全.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 6][]

点进去synchronizedMap,发现其有一个Object类型的mutex互斥对象成员,对立面的public方法使用synchronized(mutex)进行加锁.

private static class SynchronizedMap<K,V>
            implements Map<K,V>, Serializable {
            private static final long serialVersionUID = 1978198479659022715L;
    
            private final Map<K,V> m;     // Backing Map
            final Object      mutex;        // Object on which to synchronize
    
            SynchronizedMap(Map<K,V> m) {
                this.m = Objects.requireNonNull(m);
                mutex = this;
            }
    
            SynchronizedMap(Map<K,V> m, Object mutex) {
                this.m = m;
                this.mutex = mutex;
            }
    
            public int size() {
                synchronized (mutex) {return m.size();}
            }
            public boolean isEmpty() {
                synchronized (mutex) {return m.isEmpty();}
            }
            public boolean containsKey(Object key) {
                synchronized (mutex) {return m.containsKey(key);}
            }
            public boolean containsValue(Object value) {
                synchronized (mutex) {return m.containsValue(value);}
            }
            public V get(Object key) {
                synchronized (mutex) {return m.get(key);}
            }
    ...
    }

## 3.2 HashTable ##

HashTable是早期Java类库提供的Java表的实现,它是线程安全的,将涉及到修改Hashtable的方法,使用synchronized修饰.即多个线程在调用hashtable的同步方法时是按照串行化方式去运行的,性能较差.所以很少被使用了,在行为上与HashMap类似,HashTable中的代码比较简单,而且里面也没有相关的树化逻辑,攻克了上面的HashMap之后,HashTable不再是难题.可以看到其方法使用了synchronized修饰,此时获取的是方法调用者this的锁,HashTable的实现原理几乎和synchronizedMap没有差别.唯一的区别就是锁定的对象不一致而已.因此这两者在多线程环境下因为都是串行执行的,效率比较低,为了提升多线程下的执行性能,引入了ConccurentHashMap.

public synchronized V remove(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    modCount++;
                    if (prev != null) {
                        prev.next = e.next;
                    } else {
                        tab[index] = e.next;
                    }
                    count--;
                    V oldValue = e.value;
                    e.value = null;
                    return oldValue;
                }
            }
            return null;
        }

## 3.3 ConccurentHashMap ##

无论是使用Hashtable还是使用synchronized包装了的HashMap,当多线程并发的情况下,都要竞争同一把锁,导致效率极其低下,而在java5后为了改进Hashtable的痛点,ConccurentHashMap应运而生.

因为不同的对象锁之间是不会相互制约的,所以其将锁进行了细粒度化,将整锁拆解成多个锁进行优化.

### 3.3.1 早期的ConccurentHashMap ###

早期ConcurrentHashMap使用的是分段锁的技术,一段一段的去存储,给每一段配一把锁即segment,访问其中一段数据的时候,位于其它segment中的数据也能被其它线程同时访问,默认会分配16个segment,理论上比HashMap的效率提高了16倍,相比早期的HashMap,它就是将HashMap的table数组逻辑上拆分成多个子数组,每个子数组配置一把锁,线程在获取到某把分段锁之后,比如这里在获取到编号为7的segment之后,才能操作子数组,其它线程想要操作该子数组只能被阻塞,但是如果其它线程操作的其它未被占用segment的子数组是不会被阻塞的.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 7][]

### 3.3.2 java8后的ConccurentHashMap ###

其实没必要使用分段锁,或者说可以把锁拆的更细,而是table里的每个bucket都用一个不同的锁来管理,Java8之后ConccruentHashMap也确实是这么做的,它取消了分段锁,而采用了CAS+synchronized来保证并发安全,同时数据结构还是数组,链表,红黑树.

synchronized只锁定当前链表或者红黑树的首节点,这样只要hash不冲突,就可以并发.效率就会进一步的提高.

ConccruentHashMap的结构是参照了java8之后的HashMap来设计的,

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 8][]

### 3.3.3 ConccurentHashMap的源码介绍 ###

ConccurentHashMap来自JUC包的,有非常多的部分与HashMap类似,

特有变量sizeCtl是用来做大小控制的标识符,是hash表初始化或扩容时的一个控制位标志量,负数代表正在初始化,或者扩容操作,-1代表正在初始化,而-n表示有n-1个线程正在进行扩容操作,正数或者0代表hash表还没被初始化,这个数值表示初始化或者下一次扩容的大小,因为用了volatile所以sizeCtl是多线程可见的,其它线程也能看到.

其它的特有变量主要用来控制一些线程相关的并发操作.

/**
         * Table initialization and resizing control.  When negative, the
         * table is being initialized or resized: -1 for initialization,
         * else -(1 + the number of active resizing threads).  Otherwise,
         * when table is null, holds the initial table size to use upon
         * creation, or 0 for default. After initialization, holds the
         * next element count value upon which to resize the table.
         */
        private transient volatile int sizeCtl;

ConccurentHashMap是利用CAS和synchronized进行高效的同步更新数据的,我们可以来看一下put源码.

这里不能插入空的键,计算hash值,table数组元素的更新是使用CAS机制来更新的,需要不断地去做失败重试,直到成功为止.

这里先判断数组是否为空,如果为空或者length为0就将它初始化,如果不为0,就通过hash值来找到f,f是链表或者二叉树的头节点,即数组里的元素,如果f不存在就尝试通过CAS来添加,如果添加失败就break掉,进入下一次循环.

如果原先的元素已经存在了,而我们的ConccurentHashMap是处在多线程下的,有可能别的线程正在移动它(在table数组中),我们就用helpTransfer协助其扩容.

由于put方法传入的onlyIfAbsent传入的false,所以不会进入判断条件.

而是进入到else种,表示发生了hash碰撞,此时就会锁住链表或者红黑二叉树的头节点.

里就需要判断f是否是链表的头节点,如果是就会初始化链表的计数器,然后去遍历链表,并且每遍历一个节点,binCount都会加1,如果节点存在就去更新节点,如果不存在就在链表尾部去添加新的节点.

如果f是红黑二叉树的头节点,则尝试去调用红黑二叉树的操作逻辑,去尝试向树中添加节点.

如果节点是ReservationNode,就会抛出递归更新错误的异常.ReservationNode是一个保留节点,是一个占位符,不会保存实际的数据,正常情况下是不会出现的.

在jdk1.8中新的函数式有关的两个方法,ConccurentHashMap继承自Map,在Map中的computeIfAbsent与computeIfPresent两个方法中会出现ReservationNode,ConccurentHashMap通过这两个方法可以构建java本地缓存,通过构建本地缓存,来降低程序的计算量,复杂度,使代码简洁易懂.因为有缓存,所以在这里要做判断是不是保留节点(可能跟存储有关系,64位操作系统可能需要的存储空间是一个数的倍数).

最后是判断链表长度有没有到临界值,如果到达了临界值就要转化为树结构.

最后将size加上1.

public V put(K key, V value) {
            return putVal(key, value, false);
        }
    
        /** Implementation for put and putIfAbsent */
        final V putVal(K key, V value, boolean onlyIfAbsent) {
            if (key == null || value == null) throw new NullPointerException();
            int hash = spread(key.hashCode());
            int binCount = 0;
            for (Node<K,V>[] tab = table;;) {
                Node<K,V> f; int n, i, fh;
                if (tab == null || (n = tab.length) == 0)
                    tab = initTable();
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin
                }
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);
                else {
                    V oldVal = null;
                    synchronized (f) {
                        if (tabAt(tab, i) == f) {
                            if (fh >= 0) {
                                binCount = 1;
                                for (Node<K,V> e = f;; ++binCount) {
                                    K ek;
                                    if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                         (ek != null && key.equals(ek)))) {
                                        oldVal = e.val;
                                        if (!onlyIfAbsent)
                                            e.val = value;
                                        break;
                                    }
                                    Node<K,V> pred = e;
                                    if ((e = e.next) == null) {
                                        pred.next = new Node<K,V>(hash, key,
                                                                  value, null);
                                        break;
                                    }
                                }
                            }
                            else if (f instanceof TreeBin) {
                                Node<K,V> p;
                                binCount = 2;
                                if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                               value)) != null) {
                                    oldVal = p.val;
                                    if (!onlyIfAbsent)
                                        p.val = value;
                                }
                            }
                        }
                    }
                    if (binCount != 0) {
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            addCount(1L, binCount);
            return null;
        }

### 3.3.4 ConccurentHashMap put方法总结 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 9][]

别的需要注意的点(将来学习):

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 10][]

## 3.4 HashMap,Hashtable,ConccurentHashMap的区别 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 11][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70]: /images/20220221/85dabeeadc2d4b5c836f83830dee297b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 1]: /images/20220221/fd1d19431a5c49e083493a4b968331bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 2]: /images/20220221/09de2b4716c7462288f1b35b56adec6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 3]: /images/20220221/6b8c724d18134915a06b67771baefa6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 4]: /images/20220221/fa05679f32304203a1996ab0e7de2d46.png
[https_www.cnblogs.com_ysocean_p_9054804.html]: https://www.cnblogs.com/ysocean/p/9054804.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 5]: /images/20220221/03bf210696d24795b7fa2c567561d708.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 6]: /images/20220221/360e20ebeef44ae58b316aca0cb5096d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 7]: /images/20220221/501548a205f041d292df7568778e0262.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 8]: /images/20220221/24db51099eca4acbb2eeb5f6fecf9f7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 9]: /images/20220221/2f1487c03fb54d2786895c9b1fbda32f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 10]: /images/20220221/4d79d07bc1e74cfcbcef3a2b4cebd159.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3E2MTAzNzY2ODE_size_16_color_FFFFFF_t_70 11]: /images/20220221/d76f4682fe034e889994c1f912c3e636.png