List、set、Map的底层实现原理

java 中集合类的关系

参考文献：

http://zhangshixi.iteye.com/blog/674856l

https://www.cnblogs.com/leesf456/p/5308358.html

ArrayList是List接口的可变数组非同步实现，并允许包括null在内的所有元素。

底层使用数组实现

该集合是可变长度数组，数组扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量增长大约是其容量的1.5倍，这种 *** 作的代价很高。

采用了Fail-Fast机制，面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险

remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC

参考文献：

1. http://www.cnblogs.com/ITtangtang/p/3948610.htmll

2. https://www.cnblogs.com/leesf456/p/5308843.html

LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。

底层的数据结构是基于双向链表的，该数据结构我们称为节点

双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。

它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到

参考文献： http://zhangshixi.iteye.com/blog/672697

参考文献： http://blog.csdn.net/lizhongkaide/article/details/50595719

HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。

底层使用数组实现，数组中每一项是个单向链表，即数组和链表的结合体；当链表长度大于一定阈值时，链表转换为红黑树，这样减少链表查询时间。

HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对，当需要存储一个Node对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Node时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。

HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能

采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常

参考文献： http://blog.csdn.net/zheng0518/article/details/42199477

Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键

底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体

Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

synchronized是针对整张Hash表的，即每次锁住整张表让线程独占

参考文献： http://blog.csdn.net/zheng0518/article/details/42199477

ConcurrentHashMap允许多个修改 *** 作并发进行，其关键在于使用了锁分离技术。

它使用了多个锁来控制对hash表的不同段进行的修改，每个段其实就是一个小的hashtable，它们有自己的锁。只要多个并发发生在不同的段上，它们就可以并发进行。

ConcurrentHashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段(Segment)

ConcurrentHashMap完全允许多个读 *** 作并发进行，读 *** 作并不需要加锁。如果使用传统的技术，如HashMap中的实现，如果允许可以在hash链的中间添加或删除元素，读 *** 作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。

参考文献： http://zhangshixi.iteye.com/blog/673143l

HashSet由哈希表(实际上是一个HashMap实例)支持，不保证set的迭代顺序，并允许使用null元素。

基于HashMap实现，API也是对HashMap的行为进行了封装，可参考HashMap

参考文献： http://zhangshixi.iteye.com/blog/673789l

LinkedHashMap继承于HashMap，底层使用哈希表和双向链表来保存所有元素，并且它是非同步，允许使用null值和null键。

基本 *** 作与父类HashMap相似，通过重写HashMap相关方法，重新定义了数组中保存的元素Entry，来实现自己的链接列表特性。该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而构成了双向链接列表。

参考文献： http://zhangshixi.iteye.com/blog/673319l

对于LinkedHashSet而言，它继承与HashSet、又基于LinkedHashMap来实现的。LinkedHashSet底层使用LinkedHashMap来保存所有元素，它继承与HashSet，其所有的方法 *** 作上又与HashSet相同。

2021-11-10

列表是一种非连续的存储容器，有多个节点组成，节点通过一些变量记录彼此之间的关系

单链表和双链表就是列表的两种方法。

原理：A、B、C三个人，B懂A的电话，C懂B的电话只是单方知道号码，这样就形成了一个单链表结构。

如果C把自己的号码给B，B把自己的号码给A，因为是双方都知道对方的号码，这样就形成了一个双链表结构

如果B换号码了，他需要通知AC，把自己的号码删了，这个过程就是列表的删除 *** 作。

在Go语言中，列表使用 container/list 包来实现，内部的实现原理是双链表，列表能够高效地进行任意位置的元素插入和删除 *** 作。

列表初始化的两种办法

列表没有给出具体的元素类型的限制，所以列表的元素可以是任意类型的，

例如给列表中放入了一个 interface{} 类型的值，取出值后，如果要将 interface{} 转换为其他类型将会发生宕机。

双链表支持从队列前方或后方插入元素，分别对应的方法是 PushFront 和 PushBack。

列表插入函数的返回值会提供一个 *list.Element 结构，这个结构记录着列表元素的值以及与其他节点之间的关系等信息，从列表中删除元素时，需要用到这个结构进行快速删除。

遍历完也能看到最后的结果

学习地址： http://c.biancheng.net/view/35.html

原理就是线性表的插入，删除，和格式化。

由于数组是一组连续且数据类型相同的数，所以它在内存中的存储方式是以线性表的方式存储的，所以它的各项 *** 作的原理和线性表的原理是一样的。

插入算法：

int insertlist(seqlist *l,int i,elemtype b)

{

if(i>L->len)||(i<1)||(L->len>=L->listsize)

reuturn error//如果位置越界，或空间不够，出错处理

else

for(j=L->lenj>=ij++)

L->elem[j+1]=L->elem[j] //将从第i个位置的元素往后移一位

L->elem[i]=b

L->len=L->len+1 //表的长度加一

return ture

}

删除的算法：

int deletelist(seqlist *L,int i)

{

if(i>L->len)||(i<1)||(L->len>=L->listsize)

reuturn error //如果位置越界，或线性表中无元素，则出错处理

for(j=ij<=(L->len-1)j++)

L-<elem[j]=L-<elem[j+1]//找到这个元素，将其删除，并将从第i为元素往前移一位

L->len--// 表的长度减一

return ture

}

其他的算法都可以根据这两个算法推出来。

---