java 数据结构总结之 集合 collection

前言 ：

(如果你大学不好好学数据结构亦或者是死记它，为了应付考试，那将来你用到的时候，30多还会用更多的时间去重新学习它，所以理解记忆更重要！！！）但是更重要的是大学老师应该告诉怎么去理解记忆，为什么要理解记忆数据结构！！做开发这么多年天天使用arrylist ,linklist ,不知道他的底层数据结构，真是太愚蠢了！！

1, LIST （可以有重复元素的集合）

1.1? ?ArrayList??

? ? ? 1， 底层数据结构? ?动态数组? 、 或者也可以说是顺序结构线性表 （顺序表）

? ? ? ?tips： 线性表 ：:链表、栈、队列? ?；线性表是一个逻辑结构，可以有顺序表和链表两种不同的存储结构，且两种存储结构影响数据处理的效率?

? ? ? ? ? ? ? ? ?线性表分为，顺序表， 和 链表，顺序表是顺序存储的线性表， 链表则是链式存储。? ?

? ? ? ? ? ? ? ? ?顺序存储： 把逻辑上相邻的元素存储在物理位置上也相邻的位置，元素之间的关系由存储单元的相邻关系体现。

? ? ? ? ? ? ? ? 链式存储 ：（链表）概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

? ? ? ?tips ： 动态数组 和静态数组

? ? ? ? ? ? ?静态数组： java 一块固定长度的连续内存空间的数组 ，写法是 dataType []? arrayname = new dataType[lentgh] ;? 只要声明了静态数组，长度就无法改变。

? ? ? ? ? ?动态数组：根据实际需求分配动态内存空间的数组，写法是? dataType [] arrayname = new dataType[]? , 数组的长度根据需求变化而变化。增删 例如 ArrayLIst 的 add（） 和 remove（）? 方法；

? ? ? ?总结 ： 静态数组 是个适合固定长度的 查和改 操作的业务；其他的就用动态数组，适合增删 和? 查改? ！

?arrayList? 是实现了基于动态数组的数据结构，一个arrayList 集合存储在?是个连续内存中。

1， 顶一个arrayl8ist 集合 A, 并插入对象 （1，5）；

2， A.add（6) 会 将6 添加到集合的a的最后边

3， A.add(3,7) 将 7.插入到 A 集合的第三个位置，4，5，6分别向后移动一个位置，给7，插入。

4，A.remove(2) 将 集合中A的2 元素删除，同时后边的所有元素向前移动一个位置，把2空闲的位置填满，

这就可以看出，arrayList 不适合元素的增删，时间复杂度高，增删之后对应其他元素的位置也要发生改变。但适合，查找， 直接根据元素下边即可查到。

2，线程安全性，

? arrayList 是线程不安全的，vector 是线程安全的，copyonwriteArrayList 线程安全，多线程情况下可以使用，??

? vector 的实现方式和arrayList 的实现方式基本相同，不同的地方就是他是线程安全的，就是在涉及到线程不安全的，增删操作的方法上加了synchronized 关键字，因为这种方式是方法级别的，还是可以同时操作，可能添加数组时，找到了数组下边，但是进行添加时候，数组下标已经被删除了，此时数组越界异常。。。所以我们在用vector 并发编程时候还是需要手动枷锁。！

copyonwriteArrayList? 并发编程使用他，从字面上看，叫做写时候copy 就是我们在写操作的时候先考出来一份，在新数组的进行操作，操作成功后在复制回去。通过锁 + 数组拷贝 +?volatile?关键字保证了线程安全；

?就是，他在操作的时候，首先? 1， 枷锁， 2，从原数组copy, 3,在新的数组上进行操作，把新的数组复制给数组容器，4， 解锁，5，把冰箱门带上。

在某些场景下，copyonWirtearrayList 可能不是最佳选择， 当写操作较频繁，内存资源有限或者需要实时迭代器时，可以考虑使用其他线程安全集合，如concurrentHashMap 、 concurrentLinkedqueue或concurentSkipListSet等。

摘要：

　　ConcurrentHashMap是J.U.C(java.util.concurrent包)的重要成员，它是HashMap的一个线程安全的、支持高效并发的版本。在默认理想状态下，ConcurrentHashMap可以支持16个线程执行并发写操作及任意数量线程的读操作。本文将结合Java内存模型，分析JDK源代码，探索ConcurrentHashMap高并发的具体实现机制，包括其在JDK中的定义和结构、并发存取、重哈希和跨段操作，并着重剖析了ConcurrentHashMap读操作不需要加锁和分段锁机制的内在奥秘和原理

　HashMap 是 Java Collection Framework 的重要成员，也是Map族(如下图所示)中我们最为常用的一种。不过遗憾的是，HashMap不是线程安全的。也就是说，在多线程环境下，操作HashMap会导致各种各样的线程安全问题，比如在HashMap扩容重哈希时出现的死循环问题，脏读问题等。HashMap的这一缺点往往会造成诸多不便，虽然在并发场景下HashTable和由同步包装器包装的HashMap(Collections.synchronizedMap(Map<K,V> m) )可以代替HashMap，但是它们都是通过使用一个全局的锁来同步不同线程间的并发访问，因此会带来不可忽视的性能问题。庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个线程安全的高效版本 —— ConcurrentHashMap。在ConcurrentHashMap中，无论是读操作还是写操作都能保证很高的性能：在进行读操作时(几乎)不需要加锁，而在写操作时通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。特别地，在理想状态下，ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设为16），及任意数量线程的读操作。

?concurrentHashMap 本质上是一个Segment 数组，而一个Segment 又包含多个桶，每个桶包含一条由若干个Hashentry对象连接取来的链表。

HashEntry 用来封装散列映射表中的键值对。在 HashEntry 类中，key，hash和 next 域都被声明为 final 型，value 域被声明为 volatile 型。

在 ConcurrentHashMap 中，在散列时如果产生“碰撞”，将采用“分离链接法”来处理“碰撞”：把“碰撞”的 HashEntry 对象链接成一个链表。由于 HashEntry 的 next 域为 final 型，所以新节点只能在链表的表头处插入。此处只是简单的谈下， 具体还得大家仔细研究。

2， linkedList?

底层数据结构： 链表具体说是双向链表

? ?tips :?

单链表 ： 一个节点存储了当前数据和下一个数据的地址?

双链表： 不仅存储了下个数据的地址，还存了上一个数据的地址

在某些

1. LinkedList实现了?List接口

2. LinkedList的底层使用了?双向链表

3. LinkedList没有实现RandomAccess接口，因此LinkedList?不支持随机访问

4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

二、 set?

1,? 用于存储无序（存入和取出的顺序不一定相同）元素，但值不能重复。

1.1? HashSet? ?线程不安全，存取速度快，底层是以哈希表实现的。

public class Demo4 {
	public static void main(String[] args) {
		//Set 集合存和取的顺序不一致。
		Set hs = new HashSet();
		hs.add("1");
		hs.add("2");
		hs.add("3");
		hs.add("4");
		System.out.println(hs);
		// 3,1, 2, 4]
		Iterator it = hs.iterator();
		while (it.hasNext()) {
			System.out.println(it.next());
		}
	}

• 哈希表在JDK8之前是由数组+链表组成的，在JDK8之后是由数组+链表+红黑树组成的

jdk7 中， 哈希表是采用数组链表实现的，每个链表称之为桶，插入对象时，需要确定其应载表中的位置，首先要计算该对象的哈希值，然后与桶的总数取余，余数为对象载哈希表中的位置的索引。如果该桶为空，则可将对象直接插入相应的索引的通中，如果该桶已经被沾满，则需要将该对象与该桶中的所有对象进行比较，看看是否已经参组该对象，如果全部比较后钧不存在，则将其添加到该桶中（这就是拉链法，解决hash冲突），对于哈希表的实现做了些改进，通过数组链表红黑树，实现，当某个桶经常发生哈希冲突时，该链表长度将会变得非常长，下次新的对象将必须一次比较该桶中的所有对象，当桶中对象数量超过8个时，jdk8 中会将该链表转换为红黑树。

tips :?

红黑树

红黑树时一种自平衡二叉查找树，可以载o(log(o)) 时间内完成查找，插入和删除，相对于avl树来说，牺牲了部分平衡性以换取插入删除操作时少量旋转的操作，

? 红黑树的特性：

1， 每个节点要么是红色要么是黑色，

2， 根节点是黑色

3，每个叶子节点是黑色，并且空节点（还有另一种说法是，每个叶子节点都带有两个空的黑色节点（称之为黑哨兵）），如果一个节点n 只有一个左孩子，那么n的右孩子是一个黑哨兵；如果节点n只有一个右孩子，Mamet左孩子是一个黑哨兵。

4， 如果一个节点是一个红色，则它的子节点必须是黑色。

5，从一个节点到该节点的子孙节点的所有路径上 包含相同数目的黑色节点。

特性3中指定红黑树的每个叶子节点都是空节点，但是在java 实现中红黑树将使用null 代码空节点，因此遍历红黑树时看不到黑色的叶子节点，反而见到的叶子节点是红色的

特性4 保证从更节电到叶子节点的最长路径的长度不会超过任何其他路径的两倍，例如黑色高度为3 的红黑树。

?红黑树是怎么保持自平衡的，通过左旋，右旋 ，改变颜色保持。

，删除操作比较复杂，大概分为三种，

1， 删除的节点没有孩子节点，即当前节点为叶子节点，这种可以直接删除

2， 删除的节点有一个孩子节点，这种需要删除当前节点，并使用其孩子节点顶上来

3，删除节点有两个孩子节点，这种需要先找到其后继节点（树中大于节点的最小的元素）；

然后将其后继节点的呢日哦那个复制到该节点上，其后继节点就相当于该节点的替身，需要注意的是其后继节点肯定不是最小的，

? ??

?TreeSet (数据的底层实现时红黑树)

有一批数据，要求不能重复，而且要求排序，这时候需要使用TreeSet

public class Demo5 {
	public static void main(String[] args) {
		TreeSet ts = new TreeSet();
		ts.add("1");
		ts.add("4");
		ts.add("2");
		ts.add("3");
 
		System.out.println(ts); // [1, 2, 3, 4]
 
	}
}

Map? ? 是一种用于存储键值对的数据结构，它提供里一种通过键来快速查找和访问值得方式，MAP 接口有多个实现类，在常用得实现类中包含hashmap ,treeMap, 和linkedHashMap。

?1， hashMap 是 基于哈希表实现得MAP, 提供快速得插入，删除，和查找操作，他不保证元素得顺序，允许使用null 键和 null 值。

?hashmap 底层是哈希表，得map 接口实现，是常用Java集合之一，是非线程安全得，且不能保证元素的存储顺序，查询和修改得速度很快，能到O（1） 平均复杂度。

实现类TreeMap

? hashTable , 和 hashMap 一样，hashtable 也一个散列表，它存储的内容是键值对，

hashtable, 继承dictionary, 实现MAp, cloneable/ serirziavle接口。

hashtable ,的函数同步synchronized 的，所以他是线程安全的，它的 key value 都不i可以null, 此外hashtable 中的映射不是有序的。

??

?LinkedHashMap 可以看作能够记住插入元素的顺序的HashMap

底层实现：LinkHashMap 是HashMap 和 双向链表的，HashMap?

?LindkedHashMap 和HashMap 是 java Collention Framework 的重要成员，也是Map族

LindedHashMap 是HashMap 的子类（拥有HashMap 的所有特性）

LinkedHasmp 和HashMap 最多只允许一条entry 的键为Null（多条会覆盖），但允许多条Entry的值为Null

LinedHashMap 也Map 的一个非同步的实现

HashMap 是无序的,LinkedHashMap 通过维护一个额外的双向链表保证了迭代顺序

迭代顺序可以是插入顺序，也可以是访问顺序

Map基本数据结构（Entry：具体结构图在定义中）：

LinkedHashMap中的Entry增加了两个指针 before 和 after，用于维护双向链接列表
before、after用于维护Entry插入的先后顺序

next用于维护HashMap各个桶中Entry的连接顺序。
?