hashmap：数组链表红黑树：有一个链表转红黑树的过程
concurrentHashMap：由分段变为CAS算法
元素有序的、可以重复、可以为 null 的集合
1.1常见的list接口实现类 1.1.1ArrayList数据结构为可变数组，是线程不安全的；
底层操作机制源码分析：
- ArrayList中维护了一个Object类型的数组elementData,这个elementData就是当前集合的最大容量
- 当创建ArrayList没指定长度（elementData），则elementData为第一次添加则扩容为10，如需再次扩容，则扩容为当前的1.5倍
- 当创建ArrayList指定长度（elementData），如需扩容，则扩容为当前elementData的1.5倍
数据结构为可变数组，是线程安全的（同步）。Vector中的方法基本上都使用了synchronized，通常性能上较ArrayList 差。
- 如果创建时没指定长度，默认为10满了后扩展一倍容量；
- 创建时指定长度，每次直接按1倍扩容；
数据结构为双向链表，线程不安全的
- 每个linkedList的实例中都维护了first和last分别指向首节点和尾节点；
- 每个节点，里面又维护了prev指向前一个节点、next指向后一个节点、item三个属性。最终实现双向链表；
- linkedList元素的添加和删除不是通过数组完成的，相对来说效率较高；
数据结构基础之双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
Student.java public class Student implements Comparable1.3常用的方法{ private String name; private Integer age; private Date birthday; public Student(String name, Integer age, Date birthday) { this.name = name; this.age = age; this.birthday = birthday; } // 按年龄大小排序规则 @Override public int compareTo(Student o){ return this.age.compareTo(o.getAge()); } Test类 public static void main(String[] args) throws Exception{ List studentList = new ArrayList (); SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); Student student1 = new Student("啊",1,sdf.parse("1998-11-27 14:13:30")); Student student2 = new Student("不",2,sdf.parse("1996-05-28 00:00:00")); Student student3 = new Student("从",3,sdf.parse("2005-01-22 00:00:00")); Student student4 = new Student("的",4,sdf.parse("2005-01-22 00:00:00")); Student student5 = new Student("饿",5,sdf.parse("2005-01-22 00:00:00")); studentList.add(student3); studentList.add(student1); studentList.add(student4); studentList.add(student5); studentList.add(student2); //排序:如果排序对象为数组的话，调用Arrays.sort方法 //1.要比较的对象实现Comparable类重写compareTo方法 Collections.sort(studentList); //2.提供了两个参数的方法，第二个参数为比较器，Student类不用实现Comparable接口 Collections.sort(studentList, new Comparator () { @Override public int compare(Student o1, Student o2) { return o1.getAge()-o2.getAge(); } }); //遍历 //1.迭代器集合类的通用遍历方式。 Iterator iterator = studentList.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } //2.普通for循环对于ArrayList来说速度比较快。 for(int i = 0 ; i < studentList.size() ; i++) { System.out.println(studentList.get(i)); } //3.超级for循环遍历 for(Student attribute : studentList) { System.out.println(attribute); } }
// a.将List转为数组; String [] arr=new String [list.size()]; list.toArray(arr); // b.将数组转为list ArrayList< String> arrayList = new ArrayList1.4 List遍历时修改list中的元素问题(strArray.length); Collections.addAll(arrayList, strArray); // c.将list变为线程安全的 List list = Collections.synchronizedList(new ArrayList()); //d.数组排序 //1.要比较的对象实现Comparable类重写compareTo方法 Collections.sort(studentList); //2.提供了两个参数的方法，第二个参数为比较器，不用实现Comparable Collections.sort(studentList, new Comparator () { @Override public int compare(Student o1, Student o2) { return o1.getAge()-o2.getAge(); } });
在遍历集合时添加了一个元素，这样就修改了集合中的元素个数，所以会导致modCount不等于expectedModCount，这样就会报出ConcurrentModificationException异常。
public static void main(String[] args) {
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("monkey");
list.add("d");
list.add("e");
// 使用ListIterator解决上面的问题
ListIterator listIter = list.listIterator();
while (listIter.hasNext()) {
String str = (String) listIter.next();
if (str.equals("monkey")) {
listIter.add("1024");
}
}
System.out.println(list);
}
2.Set接口:
无序长度可变的数组，不允许添加重复元素，允许存储null，如果把两个相同的元素加入到同一个set中，add方法返回false；
2.1常见的set接口的实现类 2.1.1HashSet:数据结构为数组+链表+红黑树（底层是以HashMap来实现的），元素无序且唯一，线程不安全，元素可以为null；
- 添加机制：
向HashSet集合中存入一个元素时，会调用该对象的HashCode()方法来得到该对象的Hash 值，hash值转成索引决定存放位置；
若索引位置没存放元素直接添加，若存在调用eauals比较，相同就放弃添加不同就添加到链表的最后端；
在java8中若一条链表的元素个数到达TREEIFY_THRSHOLD(默认是8)，并且table数组的大小大于64就会就进行树化（红黑树）。 - 扩容机制
第一次添加时，table数组扩容到16，临界值时16加载因子（0.75）=12
如果元素个数使用到了临界值12就会扩容两倍，162=32新的临界值就是32*0.75=24 以此类推；
在java8中如果一条链表的元素个数到达TREEIFY_THRSHOLD(默认是8)，并且table数组的大小大于64就会就进行树化（红黑树）。
数据结构是数组+双向链表（底层是linkedHashMap），元素有序且唯一；
- 根据HashCode()方法来决定元素的存储位置,同时使用链表维护元素的次序.这样使得元素看起来像是以插入顺序保存的,当遍历该集合的时候,linkedHashSet将会以元素的添加顺序访问集合的元素.
- 每个linkedHashSet的实例中都维护了head和tail分别指向首节点和尾节点；
- 每个节点，里面又维护了pre指向前一个节点、next指向后一个节点。最终实现双向链表；
- linkedHashSet在迭代访问Set中的全部元素时,性能比HashSet好,但是插入时性能稍逊色于HashSet.
数据结构是红黑树（底层使TreeMap），元素有序且唯一
SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。
TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0
public class Student implements Comparable3.Map接口:{ private String name; private Integer age; private Date birthday; // 按年龄大小排序规则 @Override public int compareTo(Student o){ if( o.getAge()-this.age==0){ if( o.getName().compareTo(this.name)==0){ return 0; }else if( o.getName().compareTo(this.name)<0){ return -1; }else{ return 1; } }else if( o.getAge()-this.age<0){ return -1; }else{ return 1; } } @Override public int hashCode() { return this.name.hashCode()*this.age.hashCode(); } @Override public boolean equals(Object obj) { if (obj == null){ return false; } if (this == obj){ return true; } if (obj instanceof Student) { Student vo = (Student) obj; // 比较每个属性的值 一致时才返回true if (vo.name.equals(this.name) && vo.age.equals(this.age)){ return true; } } return false; } } Test方法 public static void main(String[] args) throws Exception{ Set set = new TreeSet (); SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); Student student1 = new Student("1",1,sdf.parse("1996-05-28 00:00:00")); Student student2 = new Student("2",1,sdf.parse("1996-05-28 00:00:00")); Student student3 = new Student("3",1,sdf.parse("1996-05-28 00:00:00")); Student student4 = new Student("4",1,sdf.parse("1996-05-28 00:00:00")); Student student5 = new Student("5",1,sdf.parse("1996-05-28 00:00:00")); //此处添加复杂类型变量时需注意实现comparable接口或者自定义比较器 set.add(student3); set.add(student1); set.add(student4); set.add(student5); set.add(student2); //遍历 //1.加强for循环遍历： for (Student student:set) { System.out.println(student.getName()+student.getAge()); } //2.迭代器遍历 Iterator iterator = set.iterator(); while (iterator.hasNext()){ Student next = iterator.next(); System.out.println(next.getName()+next.getAge()); } //去重 //依据hashCode和equals进行判断是否相等,必须重载Student类的equals和hashCode方法 //排序 参考list的排序即可 }
用于保存具有隐射关系的数据key-value；key和valus可以是任何引用类型的数据但不允许重复，key和value都可以为null；
put时将一个k-v放在一个Node中，Node中包含了hash值(根据key的值计算出的）、key(键）、value(值）和next(下一个元素的位置）；
Node实现了Map.Entry
数据结构jdk1.7数组+链表；jdk1.8数组+链表+红黑树，可以存储null键和null值，线程不安全,键值不重复
- 添加机制：
向HashMap集合中存入一个k-v时，会调用该对象的HashCode()方法来得到该对象的Hash 值，hash值转成索引决定存放位置；
若索引位置无元素直接添加，若存在调用eauals比较key是否相等，相同就直接替换value，不同就判断是树结构还是链表做出相应处理；
在java8中若一条链表的元素个数到达TREEIFY_THRSHOLD(默认是8)，并且table数组的大小大于64就会就进行树化（红黑树）。 - 扩容机制
第一次添加时，table数组扩容到16，临界值为 16加载因子（0.75）=12
如果元素个数使用到了临界值12就会扩容两倍，162=32新的临界值就是32*0.75=24 以此类推；
在java8中如果一条链表的元素个数到达TREEIFY_THRSHOLD(默认是8)，并且table数组的大小大于64就会就进行树化（红黑树）。
数据结构与hashMap相同，key和value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，
初始size为11，扩容因子为0.75，扩容：newsize = 当前容量*2+1
数据结构是数组+链表+红黑树组成
linkedHashMap 在HashMap结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。
数据结构是红黑树数据
默认是按升序排序, 查看“键”或“键值对”时，它们会被排序(次序由Comparabel或Comparator决定)。
TreeMap的特点在于，你得到的结果是经过排序的。
TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。
public static void main(String[] args) throws Exception{
Map map = new TreeMap();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Student student1 = new Student("1",6,sdf.parse("1998-11-27 14:13:30"));
Student student2 = new Student("2",6,sdf.parse("1996-05-28 00:00:00"));
Student student3 = new Student("3",6,sdf.parse("2005-01-22 00:00:00"));
Student student4 = new Student("4",6,sdf.parse("2005-01-22 00:00:00"));
Student student5 = new Student("5",6,sdf.parse("2005-01-22 00:00:00"));
map.put("2", student2);
map.put("4", student4);
map.put("5", student5);
map.put("1", student1);
map.put("3", student3);
//排序
//1.hashmap与treeMap默认根据键升序,Hashtable降序linkHashMap按照插入顺序
//2.想实现自定义根据键排序需要在创建map时传入比较器参数重写compare方法定义排序规则(只有treeMap能用)
//3.根据值遍历TreeMap,或HashMap需要先转成list使用Collections.sort(list,comparator<>)方可实现
ArrayList> list = new ArrayList>(map.entrySet());
Collections.sort(list, new Comparator>() {
@Override
public int compare(Map.Entry o1, Map.Entry o2) {
return o2.getValue().getName().compareTo(o1.getValue().getName());
}
});
for (Map.Entry mapSort:list) {
System.out.println("TreeMap的值排序遍历key= " + mapSort.getKey() + " value= " + mapSort.getValue().getName());
}
//遍历
//1.先遍历key后取值;通过Map.keySet遍历key和value：
for (String key:map.keySet()) {
Student value = map.get(key);
System.out.println("key:"+key+" vlaue:"+value.getName());
}
//2.通过Map.entrySet使用iterator遍历key和value：
Iterator> iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry entry = iterator.next();
System.out.println("key= " + entry.getKey() + " value= " + entry.getValue().getName());
}
//3.推荐，尤其是容量大时:通过Map.entrySet遍历key和value
for (Map.Entry entry:map.entrySet()){
System.out.println("key= " + entry.getKey() + " value= " + entry.getValue().getName());
}
//4.通过Map.values()遍历所有的value，但不能遍历key
for (Student value:map.values()) {
System.out.println("value= " + value.getName());
}
}
3.3HashMap 和Hashtable 的区别?
a.HashMap 没有排序，允许一个null 键和多个nul值(会覆盖原先null键对应的值),而Hashtable 不允许；
b.HashMap 把Hashtable 的contains 方法去掉了，改成containsvalue 和containsKey,因为contains 方法容易让人引起误解；
c.Hashtable 继承自Dictionary 类，HashMap 是Map 接口的实现；
d.Hashtable 的方法是Synchronize 的，而HashMap 不是，在多个线程访问Hashtable 时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。Hashtable 和HashMap 采用的hash/rehash 算法大致一样，所以性能不会有很大的差异
都是线程安全的Map; HashTable使用的synchronized对方法加锁，实际锁住的是整个对象；而ConcurrentHashMap使用的是lock，采用了分段(16段segment)锁的设计，只有在同一个分段内才存在竞态关系，不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计，分段锁大大的提高了高并发环境下的处理能力。
ConcurrentHashMap要避免调用size()和containsValue()方法，会对整个Map进行扫描。
包括Vector和HashTable。后来在JDK1.2也引入一个功能与之类似的类，这些同步的封装容器类是由Collections.synchronizedXXX等工厂方法创建的。这些类实现线程安全的方式是:将他们的状态封装起来，对每个公有方法都进行同步(方法加synchronized)，使得每次只有线程能访问容器的状态。
存在问题
同步容器类虽然是线程安全的，但是某些情况下需要加同步来保护复合操作(也就是一个方法中对容器进行多个操作)，有可能在两次操作的中间时间容器被修改造成异常
解决方法:对每个操作元素的方法进行同步(加synchronized)
同步容器(上面的Vector和HashTable)将所有对容器状态的访问都串行化，以实现它们的线程安全。这种方法的代价是严重降低并发性，当多个线程竞争容器的锁时，吞吐量将严重降低。
并发容器类是针对多个线程并发访问设计的在新的ConcurrentHashMap接口中增加了一些对常见复合操作的支持，例如若没有则添加、替换、以及有条件删除等。(并发容器代替同步容器可以极大地提高伸缩性并降低风险)
ConcurrentHashMap:底层采用分段的数组+链表实现，线程安全
- 1.7中（分段锁思想）
- 通过把整个Map分为N个Segment，保证了线程安全并且效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
- Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
- 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
- 扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容
- 1.8中数组+链表(hash冲突时形成链表，尾插法)+红黑树（链表节点数>=8时转成红黑树） 结构。
- CAS+Synchronized来保证并发更新的安全，
写入时复制(copy-on-write)通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个 新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的 读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。 缺点就是每次修改容器都会复制底层数组，这需要一定的开销，特别是当容器规模较大的时候。仅当迭代操作远远多于修改操作，才应该使用"写 入时复制"容器。5.3CopyonWriteArraySet
