集合ja

虽然经常使用ja集合，但是在工作中对公司信息管理系统的开发影响不大，但是在一些特殊的开发场景中还是很有必要的

了解更多有关不同特征的信息。

Ja的集合主要包括链表、集合和映射。

List、Set从集合接口继承，Map是一个独立的接口。

List下有ArrayList，LinkedList和Vector。

Set下有hashSet，linked HashSet，HashMap，LinkedHashMap，TreeSetMap，Hashtable。

摘要:连接接口:

1.列表是有序且可重复的。

ArrayList:优点:底层数据结构是数组，查询快，增删慢。缺点:线程不安全，效率高。

LinkedList:优点:底层数据结构是链表，查询慢，增删快。缺点:线程不安全，效率高。

Vector:优点:底层数据结构是数组，查询快，增删慢。缺点:线程安全，效率低。

2.集合是无序且唯一的

(1)HashSet:底层数据结构是哈希表。(无序，唯一)如何保证元素的唯一性？1.依靠两个方法:hashCode()和equals()。

HashSet底层数据结构通过哈希表实现，元素无序且唯一，线程不安全，效率高。它可以存储空元素，元素的唯一性取决于存储的元素类型是否重写了hashCode()和equals()方法。如果不重写这两个方法，就不能保证元素的唯一性。

实现独特性的比较过程:

1.存储元素时，将使用hash()算法函数生成一个int哈希值，然后比较存储元素的哈希值。如果散列不相等，它们一定是不同的对象。2.hashCode值相同，然后比较equals方法。3 .等号相同，对象相同。(不需要存储)(2)LinkedHashSet:底层数据结构是链表和哈希表。(FIFO插入是有序且唯一的)1。元素按链表2排序。元素在哈希表中是唯一的。

LinkedHashSet的底层数据结构是通过链表和哈希表实现的。链表保证元素的顺序与存储顺序一致，哈希表保证元素的唯一性。线程是不安全和高效的。

(3)TreeSet:底层数据结构是一棵红黑树。(独特，有序)1。如何保证元素的有序性？自然排序比较器排序2。如何保证元素的唯一性？根据比较的返回值是否为0。

TreeSet的底层数据结构是用红黑树实现的，元素是唯一的，并且已经按顺序排列。唯一性还需要重写hashCode和equals()方法，二叉树结构保证了元素的顺序。根据构造方法的不同，可以分为自然排序(无参数构造)和比较器排序(参数构造)。自然排序要求元素必须实现Compareable接口，并在内部重写compareTo()方法。元素可以通过比较返回的int值来判断排序顺序，返回0表示两个对象相同，不需要存储。比较器行需要在TreeSet初始化时传入一个实现比较器接口的比较器对象，或者使用匿名内部类创建一个新的比较器对象，并在内部重写compare()方法；

红黑树:

在学习红黑树之前，我们需要了解下二叉查找树(BST)。

二叉查找树

要了解二叉查找树，二叉查找树有什么特点？

1，左子树上所有节点的值都小于或等于他的根节点的值。

2.右子号上所有节点的值都大于或等于他的根节点的值。

3.左右子树也必须分别是二进制排序树。

让我们看看下面的树。这是典型的二叉查找树。

红黑树

红黑树是一种平衡的二叉查找树。说他平衡，就是不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特点外，它还具有以下特点:

1.节点为红色或黑色。

2.根节点是黑色的

3.每个叶子的节点是黑色空节点(空)。

4.每个红色节点的两个子节点是黑色的。

5.从任何节点到它的每个叶子的所有路径都包含相同的黑色节点。

看下图，是典型的红黑树:

TreeSet的两种排序方式比较

1.默认情况下，基本数据类型按升序排序。

2.自定义排序

(1)自然排序:在Comparable接口中重写Compareto方法。

(2)比较器排序:重写比较器接口中的Compare方法。

Compare(T o1，T o2)比较用于排序的两个参数。O1:代表当前添加的数据o2:代表集合中已经存在的数据0:代表o1 == o2-1(反向输出):O1；O2 1:o1-o2(升序)-1: O2-O1(降序)

示例1:

1 import ja.util.Comparator; 2 import ja.util.Set; 3 import ja.util.TreeSet; 4 5 public class Test { 6 public static void main(String[] args) { 7 8 /** 9 * 自定义规则的TreeSet10 * 客户端排序：自己写一个比较器，转给TreeSet11 *12 * 比较规则13 * 当TreeSet集合添加数据的时候就会触发比较器的compare()方法14 */15 Comparator<Integer> comp = new Comparator<Integer>() {16 /**17 * o1 当前添加的数据18 * o2 集合中已经存在的数据19 * 0： 表示 o1 == o220 * -1 ： o1 < o221 * 1 : o1 > o222 */23 @Override24 public int compare(Integer o1, Integer o2) {25 System.out.println(o1+"–"+o2);26 return o2 -o1; //输出53 33 10，降序排序27 // return 0; //只输出一个元素：3328 // return -1; //输出53 10 33，倒序输出29 // return 1; //输出33 10 5530 }31 };32 33 Set<Integer> s2 = new TreeSet<>(comp);34 s2.add(33);35 s2.add(10);36 s2.add(55);37 38 System.out.println(s2); //输入53 33 10，降序排序39 40 }41 }

示例2:

1 import ja.util.Comparator; 2 import ja.util.Iterator; 3 import ja.util.Set; 4 import ja.util.TreeSet; 5 6 /** 7 * 使用TreeSet和Comparator（使用匿名类），写Test.ja 8 * 要求：对TreeSet中的元素 9 * 1，2，3，4，5，6，7，8，9，10进行排列，10 * 排序逻辑为奇数在前偶数在后，11 * 奇数按照升序排列，偶数按照降序排列12 * 输出结果：1 3 5 7 9 10 8 6 4 213 */14 public class Test {15 public static void main(String[] args) {16 Set<Integer> s = new TreeSet<>(new Comparator<Integer>() {17 //重写compare方法18 @Override19 public int compare(Integer o1, Integer o2) {20 System.out.println("o1="+o1+" o2="+o2);21 if(o2%2==0){22 if (o1%2==0){23 return o2 -o1;24 }else{25 return -1;26 }27 }else {28 if (o1%2==0){29 return 1;30 }else{31 return o1 -o2;32 }33 }34 35 36 }37 });38 39 s.add(2);40 s.add(6);41 s.add(4);42 s.add(1);43 s.add(3);44 s.add(5);45 s.add(8);46 s.add(10);47 s.add(9);48 s.add(7);49 50 Iterator iterator = s.iterator();51 52 while(iterator.hasNext()){53 System.out.print(iterator.next()+" ");54 }55 56 }57 }

输出结果:

3.Map接口:

映射用于存储具有映射关系的数据。Map存储两组数据:key和value，都可以做任意引用类型的数据，但是key不能重复。所以你可以通过指定键得到相应的值。

Map接口有四个重要的实现类，分别是HashMap、LinkedHashMap、TreeMap和HashTable。

TreeMap是有序的，HashMap和HashTable是无序的。

Hashtable的方法是同步的，但是HashMap的方法不是同步的。这是两者的主要区别。

HashMap

Map主要用来存储键值对，根据键获取值，所以键不允许重复，但值允许重复。HashMap是最常用的映射。它根据key的HashCode值存储数据，根据key可以直接得到它的值，所以访问速度很快。HashMap最多允许一条记录带有空键；允许多条记录具有空值；HashMap不支持线程的同步，即多个线程可以随时同时写HashMap；这可能会导致数据不一致。如果需要同步，可以使用Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。HashMap是基于哈希表结构实现的。当一个对象被当作一个键时，hasCode和equals方法必须重写。

LinkedHashMap

LinkedHashMap继承自HashMap，主要是利用链表来扩展HashMap类。HashMap中的项目是无序的，但是在LinkedHashMap中，元素可以按照它们入图中的顺序或者它们最后被访问的顺序进行排序。

TreeMap

TreeMap是基于红黑树数据结构的实现，可以使用Comparable或Comparator接口对键值进行排序。TreeMap继承自AbstractMap，并实现了从SortedMap继承的NigableMap接口。SortedMap是Map的子接口，可以保证Map中的项目排列有序。

在实际使用中，如果更新图时不需要保持图中元素的顺序，使用HashMap如果您需要保持图中元素的插入顺序或访问顺序，请使用LinkedHashMap如果您需要根据键值对图表进行排序，请使用TreeMap。

Hashtable

Hashtable与前面介绍的HashMap非常相似，它也是一个Hashtable，存储键值对的映射。区别在于Hashtable是从Dictionary继承的，Hashtable中的函数是同步的，这意味着它是线程安全的。此外，Hashtable中的键和值都不能为空。

适用场景分析:HashSet是基于Hash算法实现的，性能通常优于TreeSet。为快速搜索而设计的集合，我们通常应该使用HashSet，只有在需要排序功能的时候才使用TreeSet。

如何选择:

遍历map实例

1 import ja.util.HashMap; 2 import ja.util.Iterator; 3 import ja.util.Map; 4 5 public class Test { 6 7 public static void main(String[] args) { 8 Map<String, String> map = new HashMap<String, String>(); 9 map.put("first", "linlin"); 10 map.put("second", "好好学ja"); 11 map.put("third", "sihai"); 12 map.put("first", "sihai2"); 13 14 15 // 第一种：通过Map.keySet遍历key和value 16 System.out.println("===================通过Map.keySet遍历key和value:==================="); 17 for (String key : map.keySet()) { 18 System.out.println("key= " + key + " and value= " + map.get(key)); 19 } 20 21 // 第二种：通过Map.entrySet使用iterator遍历key和value 22 System.out.println("===================通过Map.entrySet使用iterator遍历key和value:==================="); 23 Iterator<Map.Entry<String, String>> it = map.entrySet().iterator(); 24 while (it.hasNext()) { 25 Map.Entry<String, String> entry = it.next(); 26 System.out.println("key= " + entry.getKey() + " and value= " 27 + entry.getValue()); 28 } 29 30 // 第三种：通过Map.entrySet遍历key和value 31 System.out.println("===================通过Map.entrySet遍历key和value:==================="); 32 for (Map.Entry<String, String> entry : map.entrySet()) { 33 System.out.println("key= " + entry.getKey() + " and value= " 34 + entry.getValue()); 35 } 36 37 // 第四种：通过Map.values()遍历所有的value，但是不能遍历键key 38 System.out.println("===================通过Map.values()遍历所有的value:==================="); 39 for (String v : map.values()) { 40 System.out.println("value= " + v); 41 } 42 } 43 44 } 重点问题重点分析:（一）说说List,Set,Map三者的区别？List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。Map(用Key来搜索的专家): 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。（二）Arraylist 与 LinkedList 区别?1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index) 方法)。5. 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

1.ArrayList是基于动态数组的数据结构，LinkedList是基于链表的数据结构。

2.对于get和set的随机访问，ArrayList优于LinkedList，因为LinkedList移动指针。

3.对于添加和删除操作，LinedList更占优势，因为ArrayList要移动数据。尽量避免同时遍历和删除集合。因为这将改变集合的大小；

（三）ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？

Vector类的所有方法都是同步的。两个线程可以安全地访问Vector对象，但是当一个线程访问Vector时，代码需要花费大量时间来同步。

Arraylist不是同步的，所以在不需要线程安全的情况下，建议使用Arraylist。

（四）说一说 ArrayList 的扩容机制吧

https://github . com/snail climb/Ja guide/blob/master/docs/Ja/collection/ArrayList-grow . MD

（五）HashSet与TreeSet与LinkedHashSet对比

HashSet不能保证元素的排列顺序，顺序可能会变，不同步。集合元素可以为null，但只能放入一个nullTreeSet。Treeset是SortedSet接口的唯一实现类，它可以保证集合元素处于已排序状态。TreeSet支持两种排序方式，自然排序和自定义排序，其中自然排序是默认的排序方式。应该添加到树集中的是同一个类的对象。TreeSet判断两个对象不相等的方式是通过equals方法返回false，或者不通过CompareTo方法返回0。自然排序使用待排序元素的CompareTo(Object obj)方法比较它们之间的大小关系，然后按照升序排列元素。自定义排序自然排序根据集合中元素的大小按升序排列。如果要自定义排序，就要使用Comparator接口，实现int compare(To1，To2)的方法。LinkedHashSet集合也根据元素的hashCode值来确定元素的存储位置，但它也使用链表来维护元素的顺序。这使得元素看起来是按照插入顺序保存的，也就是说，在遍历集合时，LinkedHashSet将按照添加的顺序访问集合中的元素。在迭代访问集合中的所有元素时，LinkedHashSet的性能优于HashSet，但在插入时略逊于hashSet。

（六）LinkedHashMap和HashMap，TreeMap对比

Hashtable类似于HashMap，它继承自Dictionary类，但区别在于它不允许键或值为空的记录；它支持线程的同步，即任何时候只有一个线程可以写Hashtable，这也导致了Hashtable写的很慢。HashMap是最常用的映射。它根据键的HashCode值存储数据，根据键可以直接得到它的值。访问速度快，遍历时获取数据的顺序完全随机。LinkedHashMap保存记录的插入顺序。当迭代器用于遍历LinkedHashMap时，首先获得的记录必须首先插入。您也可以在构造时使用参数，并根据应用程序的数量对它们进行排序。遍历的时候会比HashMap慢，但是有一个例外。当HashMap的容量较大，实际数据较少时，可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只与实际数据有关，与容量无关，HashMap的遍历速度与他的容量有关。TreeMap实现了SortMap接口，可以根据键对其保存的记录进行排序。默认情况下，键按升序排序，您也可以指定排序比较器。当迭代器用于遍历TreeMap时，获得的记录是排序的。我们用的最多的是HashMap，HashMap中存储的键值对取出来是随机的。HashMap是在地图中插入、删除和定位元素的最佳选择。TreeMap取出的是排序后的键值对。但是如果你想按照自然顺序或者自定义顺序遍历键，那么TreeMap更好。LinkedHashMap是HashMap的子类。如果输出的顺序和输入的顺序相同，可以用LinkedHashMap实现，也可以按读取顺序排列，像可以应用在连接池中。

（七）HashMap 和 Hashtable 的区别线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。（八）HashMap 和 HashSet区别

如果你读过HashSet源代码，你应该知道底层HashSet是基于HashMap实现的。(HashSet的源代码非常非常少，因为除了clone()、writeObject()和readObject()是HashSet要实现的，其他的方法都是直接调用HashMap中的方法。

（九）HashSet如何检查重复

当您将一个对象添加到HashSet中时，HashSet将首先计算该对象的hashcode值，以确定添加该对象的位置，还会将其与其他添加对象的hashcode值进行比较。如果没有匹配的hashcode，HashSet将假定对象不会重复出现。但是如果发现hashcode值相同的对象，就会调用equals()方法检查hashcode相同的对象是否真的相同。如果两者相同，HashSet不会让join操作成功。(摘自我的ja启蒙书《头拳Ja》第二版)

hashCode()和equals()的相关规定:

如果两个对象相等，则hashcode一定也是相同的两个对象相等,对两个equals方法返回true两个对象有相同的hashcode值，它们也不一定是相等的综上，equals方法被覆盖过，则hashCode方法也必须被覆盖hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。（十）HashMap的底层实现JDK1.8之前

在JDK1.8之前，HashMap的底层是数组和链表的组合，也就是链表的hash。HashMap通过扰动函数处理后的key的hashCode获得哈希值，然后通过(n-1) & hash(其中n指数组的长度)判断当前元素的存储位置。如果当前位置有元素，则判断该元素与要存储的元素的哈希值和密钥是否相同，如果相同，则直接覆盖，如果不相同，则通过zipper方法解决冲突。

所谓扰动函数，指的是HashMap的hash方法。Hash方法，也就是扰动函数，用来防止一些实现不好的hashCode()方法，换句话说，使用扰动函数后可以减少碰撞。

HashMap实现原理(更好的描述):HashMap以键值对的形式存储元素，但是在调用put方法时，HashMap会通过hash函数计算出键的hash值，然后通过hash值判断当前元素的存储位置&(HashMap.length-1)。如果当前位置有元素，则需要判断当前元素是否与要存储的密钥相同。如果有，也是一样的。在JDk1.8中，当链表的长度大于8时，链表被转换为红黑树。

JDK 1.8 HashMap的哈希方法源代码:

与JDK 1.7哈希法相比，JDK 1.8哈希法更加简化，但原理不变。

1 static final int hash(Object key) {2 int h;3 // key.hashCode()：返回散列值也就是hashcode4 // ^ ：按位异或5 // >>>:无符号右移，忽略符号位，空位都以0补齐6 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);7 }

对比JDK1.7的hash源代码。

1 static int hash(int h) {2 // This function ensures that hashCodes that differ only by3 // constant multiples at each bit position he a bounded4 // number of collisions (approximately 8 at default load factor).5 6 h ^= (h >>> 20) ^ (h >>> 12);7 return h ^ (h >>> 7) ^ (h >>> 4);8 }

相比JDK1.8的hash方法，JDK 1.7的hash方法性能会差一点，因为毕竟被扰动了四次。

所谓“拉链法”，就是把链表和数组结合起来。也就是说，创建一个链表数组，数组中的每个单元格都是一个链表。如果有散列冲突，只需将冲突的值添加到链表中。

JDK1.8之后

与之前的版本相比，JDK1.8之后，在解决哈希冲突方面有了很大的变化。当链表的长度大于阈值(默认为8)时，链表被转换为红黑树以减少搜索时间。

JDK1.8以后的TreeMap、TreeSet、HashMap都是使用红黑树。红黑树是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成线性结构。

（十一）HashMap 的长度为什么是2的幂次方

为了使HashMap访问高效，冲突最小化，也就是尽可能均匀地分布数据。上面我们提到过，哈希值的范围是-2147483648到2147483647，加起来大概有40亿个映射空。只要哈希函数映射均匀松散，一般应用中很难发生碰撞。但问题是一个40亿长度的数组放不进内存。所以这个哈希值不能直接使用。在使用它之前，你必须对数组的长度取模，余数可以用于要存储的位置，也就是对应的数组下标。这个数组下标的计算方法是“(n-1) & hash”。(n代表数组长度)。这也解释了为什么HashMap的长度是2的幂。

这个算法应该怎么设计？

我们可以首先想到采用%余数的运算来实现。但重点是:“如果余数(%)运算中的除数是2的幂，则相当于其除数减一的AND (&)运算(即hash%length==hash&(length-1)的前提是长度是2的幂；)。”而使用二进制位运算&相比%可以提高运算效率，这也解释了为什么HashMap的长度是2的幂。

（十二）HashMap 多线程操作导致死循环问题

主要原因是并发的重散列会造成元素间的循环链表。不过这个问题在jdk 1.8之后得到了解决，但是仍然不建议在多线程下使用HashMap，因为在多线程下使用HashMap仍然存在数据丢失等其他问题。在并发环境中推荐使用ConcurrentHashMap。

ReHash:一般来说，当哈希表的容器中有数据要插入时，会检查容量是否超过设定的thredhold。如果超过，就需要增加哈希表的大小，但是这样一来，整个哈希表中的所有元素都需要重新计算。这叫老调重弹，成本挺大的。

（十三）ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap和Hashtable的区别主要体现在线程安全的实现方式上。

底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁,效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者对比图:

哈希表:

JDK1.7的ConcurrentHashMap：（十四）ConcurrentHashMap线程安全的具体实现方式/底层具体实现JDK1.7（上面有示意图）

首先，将数据分成段进行存储，然后为每段数据分配一个锁。当一个线程占用锁访问一段数据时，其他段的数据也可以被其他线程访问。

ConcurrentHashMap由段数组结构和HashEntry数组结构组成。

Segment实现了ReentrantLock，所以Segment是一个可重入的锁，起着锁的作用。HashEntry用于存储键值对数据。

静态类段& ltk，V & gt扩展可重入锁实现serializable { } concurrent hashmap包含段数组。Segment的结构类似于HashMap，是一种数组和链表结构。一个段包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个段守护一个HashEntry数组中的元素。修改HashEntry数组的数据时，必须先获取对应段的锁。

JDK1.8 （上面有示意图）

ConcurrentHashMap取消段锁，采用CAS和synchronized保证并发安全。数据结构类似HashMap1.8，数组+链表/红黑二叉树。Ja 8将链表(寻址时间复杂度为O(N))在长度超过一定阈值(8)时，转换为红黑树(寻址时间复杂度为O(log(N))。

Synchronized只锁当前链表或红黑二叉树的第一个节点，所以只要哈希不冲突，就不会有并发，效率会提高n倍。

（十五）comparable 和 Comparator的区别comparable接口实际上是出自ja.lang包 它有一个 compareTo(Object obj)方法用来排序comparator接口实际上是出自 ja.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

通常，当我们需要对集合使用定制排序时，我们必须重写compareTo()方法或compare()方法。当我们需要对一个集合实现两种排序方法时，比如对一个song对象中的歌名和歌手名使用一种排序方法，我们可以重写compareTo()方法，使用自制的Comparator方法，或者使用两个Comparator对歌名和歌手名进行排序。第二个意味着我们只能使用Collections.sort()的两个参数版本。