1：collection 下面有list set
线性表包含两者 顺序表和链表
其中List属于线性表的一种。
list 下面有arrayList LinkedList vector
arrayList 下面是一个动态数组，元素在内存中是按照顺序排列的。 初始容量为10.当容量不足的时候，就会扩容为原来的0.5倍。
LinkedList 是链表实现的数组。是一个双向链表。
Vector 其实就是把arrayList里面的部分方法进行了synchronized加锁处理。但是在扩容上不是一样的，扩容是直接扩容1倍
Set下面有TreeSet HashSet
TreeSet 底层是二叉树的实现，原理是因为在插入数据之前会先对其进行比较，有一个Compareable方法。
HashSet 底层是Hash表的实现，保证完全有序，LinkedHashSet.HashSet底层声明了一个HashMap
Hash表采用的是链地址法来解决冲突，是一个数组+++链表的形式
需要重写equal++hashCode方法来保证数据唯一。
Map
map里面包含了hashMap TreeMap
HashMap 底层其实还是一个数组，容量是16.有个加载因子是0.75；但是里面保存的数据有可能是null。
当加入新元素的时候，就会创建一个Node对象，指针域就会指向下一个添加的对象，数据域就保存了新加入的data。
也有可能是单向链表，还有可能是红黑树。
1、计算key的hash值，算出元素在底层数组中的下标位置。
2、通过下标位置定位到底层数组里的元素（也有可能是链表也有可能是树）。
3、取到元素，判断放入元素的key是否==或equals当前位置的key，成立则替换value值，返回旧值。
4、如果是树，循环树中的节点，判断放入元素的key是否==或equals节点的key，成立则替换树里的value，并返回旧值，不成立就添加到树里。
5、否则就顺着元素的链表结构循环节点，判断放入元素的key是否==或equals节点的key，成立则替换链表里value，并返回旧值，找不到就添加到链表的最后。
在1.7的时候，采用链地址法来解决Hash冲突。还是单向链表和数组
在1.8的时候，为了提高效率，当链表长度超过8的时候，会开始转换为红黑树。
网友评论