Map、List等集合

编程思想是相通的，只是实现方式有所不同。

       数据库中，我们常常用索引来找到具体某个值，当然会经常用联合索引。而在开发中，常常会有种情况：集合的key使用自定义类对象，需要自己实现hashCode()和equal()方法。

 

再来看看Map、List、Set等集合的实现：

一、Map，以hashMap为例，

1）初始化为长度16的数组，数组每个元素为一个链表对象。

2）当新建链表元素个数超过threshold，数组长度就扩展2倍。

3）当put时候，用if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 来判断是否(Object) key相等。

int threshold = (int)Math.min(capacity(16) * loadFactor(0.75f), MAXIMUM_CAPACITY(1 << 30) + 1);

另外，在java8中，HashMap加入了红黑树结构，当链表元素较多(默认8个)时，链表就会转化为红黑树。

而TreeMap实现也是基于红黑树的。可参考 

TreeMap：由红黑树实现，与HashMap不同，他内部元素不是数组，而是一个树型结构。身为排序二叉树，所以他是有序的。

 

二、List，以ArrayList为例，

1）初始化为长度10的数组，数组每个元素为一个Object。

2）当新添加对象的坐标index大于数据长度，就扩展增加当前数组1/2的长度。

3）当add时候，已有对象的size++，超过数组长度就扩展，当调用set(int index, E element)方法时，传值大于新添加对象的坐标时会报错。

 

三、Set，以hashSet为例，

1）其实用一个HashMap成员变量来实现，所以特性和hashMap基本一致。

而其他Set实现类等也是如此，比如TreeSet用TreeMap实现。

 

并发：

1、可以使用concurrent包下面的类，比如ConcurrentHashMap<K, V>和CopyOnWriteArrayList<E>等。

2、自己加锁并发。其中用Iterator遍历时，增删元素时也需要对集合加锁。

 

jdk1.7以及之前版本ConcurrentHashMap实现：Segment锁分段。每个Segment下面是多个Node，jdk7是Segment+HashEntry。

jdk1.8版本ConcurrentHashMap实现：采用Node + CAS + Synchronized，有点像java8的hashmap，使用数组+链表+红黑树，保留锁分段思想。使用较多CAS算法（即unsafe.compareAndSwapInt(this, valueOffset, expect, update)），这样可非阻塞无锁插入，但在默认操作hash值相同的链表还是会synchronized头结点上锁，将新值放在node最后一个后面，这样才能保证线程安全，和以前一样。

put方法：1.6直接获取锁，1.7自旋锁(UNSAFE.get)，等待其他人操作完，1.8是链表为null直接cas乐观锁，否则Node链表加锁。

get方法：1.6乐观锁，直接获取值，为null则可能正处于put，需要再加过判断一次。1.7HashEntry的乐观锁(UNSAFE.get)。1.8Node的乐观锁(UNSAFE.get)。

针对：

get操作的高效之处在于采用分段锁，且整个get过程不需要加锁，除非读到的值是空的才会加锁重读，特性如下：

1、写用分段锁：每个Segment包含一个数组元素，每个元素是一个HashEntry<K,V>的链表，而且put添加元素时放在头部，不影响读取。至于remove中间元素，会设置链表元素的next属性(volatile修饰)。

2、get操作不加锁：get方法里将要使用的共享变量都定义成volatile，如用于统计当前Segement大小的count字段和用于存储值的HashEntry的value。定义成volatile的变量，能够在线程之间保持可见性，能够被多线程同时读，并且保证不会读到过期的值，但是只能被单线程写（有一种情况可以被多线程写，就是写入的值不依赖于原值），在get操作里只需要读不需要写共享变量count和value，所以可以不用加锁。之所以不会读到过期的值，是根据java内存模型的happen before原则，对volatile字段的写入操作先于读操作，即使两个线程同时修改和获取volatile变量，get操作也能拿到最新的值，

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

        HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
}