单列
list
ArrayList
add方法
如果添加的时候集合的长度足够就.将添加的东西,添加进去.长度+1
如果集合的长度等于数组的长度.就进行扩容.扩容的大小是原长度的一半.数组原长度+扩容的长度
防止并发修改异常.在变量的父类中声明.modCotun++记录集合修改的次数.防止迭代器迭代集合的发生修改异常.
remove方法
删除一个元素,集合整体向前移一位,将最后一位元素设置为null防止内存泄露.然后在修改长度.并记录修改次数.然后返回删除的元素.
底层是数组增删慢,查询快.
linkedList
底层是链表,增删快,查询慢.
Voctor
优点线程安全.其他增删慢,查询慢
有索引.存取一致,可以有重复的数.
set
存取无序,不可重复
HashSet
底层hashmap
LinkedHashset
是set的子类,底层是linkedhashmap
TreeSet
存取有序.可以自定义排序
双列
map
HaShMap
添加
1.8
结构
数组加链表加红黑树
为什么要加入红黑树
因为红黑树查询和新增都不错.
当链表长度大于或者等于8的时候还要数量要大于64个会变成红黑树,如果链表长度大于8小于64就进行扩容处理.,当长度小于或者等于6的时候会变成链表.
为什么变成红黑树是要链表8个,而取消链表要6个?
是为了防止短时间频繁的变化,如果是相同的个数,当刚刚好到达这个数,是变还是不变?
存放在链表的数是以尾插法,因为头插法在高并发的时候容易出错.在添加完以后要遍历,查看是否要可以变成树.
1.7
结构
数组加链表
如果hashcode与运算的(&)存储时得到数组索引有hash冲突.就把新存储的数当做链表的头.链表是跟着头走的.头在什么位置链表就在什么位置.就把头的位置替换以前头的位置.这就是头插法(链表头插法是最快的)
1:存放的key进行hashcode然后在与(&)运算(与运算的数量就是扩容数)得到数组索引.如果没有hash冲突把kay存入到数组中.
3:当存储的数到达一定的数量(容量*因子)时进行扩容.扩容以后再进行添加
2:如果hashcode与运算的(&)存储时得到数组索引有hash冲突. 1.7版 就把新存储的数当做链表的头.链表是跟着头走的.头在什么位置链表就在什么位置.就把头的位置替换以前头的位置.这就是头插法(链表头插法是最快的).1.8版存放在链表的数是以尾插法,因为头插法在高并发的时候容易出错.在添加完以后要遍历,查看是否要可以变成树.
&的计算
为什么不用取余而用与?
与运算快一些
在添加的时候if比较的顺序
先比较hashcode(快速的排除大部分hashCode不相等的数,因为hashcode速度快)然后在equals比较值.之所以equals在后面因为equals的耗时长一些.
计算完hashCode为什么还要右移?
因为&运算时高位数没有参与运算.所有右移让高位和地位进行异或(^)运算.在进行&运算.让hashCode的离散度更高.
容量与扩容
扩容
默认的因子是0.75
容量
默认的扩容为16,每次扩容都数两倍
扩容再1.7中只有数量达到一定的数量(就是容量*因子)才扩容.在1.8中加了一个条件.就是链表长度到达8个而且数量小于64个时也会扩容处理.
扩容是给数组的因为数组是有长度限制的,而链表是没有长度限制的.扩容也就是重新申请一片空间.
在1.7中扩容比1.8扩容多一个条件,多的条件就是,当你的数量到达扩容的条件的时候.还需要的就是你添加的数算出的索引位置已经被占用了.如果没有被占用就还是不扩容的.(离散度的问题).这个条件没有多大的用处所以在1.8中就没有了.
1.7扩容以后存储的位置.是用hashcode重新&运算索引.然后存储.
1.8中扩容以后存储的位置,是优化了1.7的.因为扩容是两倍,二进制中就是加一位数,索引的二进制加的一位数一定是1,所有决定存储位置的就是hashcode进行^运算加的那一位数.所有只要判断加的那一位数是1还是0,如果是1就在原索引加扩容数(扩容后的容量的一半)这就是存储位置的索引.如果是0就不要动位置.
设置容量和因子
在进行存储的时候才进行初始化
无论你传是什么容量,大于或者等于的2的次方数.比如你设置的容量是5 他就是2的立次方数8.如果你设置的是10 大于10 的2的立次方数是16.
为什么设置的容量必须是2立次方数,扩容必须是两倍?
为了在计算hashcode的与(&)运算,获取索引的位置不出错.所有必须是2的立方数.扩容也必须是两倍的原因.
线程不安全
null放在索引0,只要有null就存储在索引0的位置
HashTable
线程安全的,不可存null
LinkedHashMap
是Hashmap的子类
可以排序
键是不可以重复.值是可以重复的
数组和链表
数组
优点:内存地址连续,所有查找数据的效率比较高.
缺点:在存储的之前要申请一块连续的内存空间,必须确定他的空间大小,无法改变空间大小.
链表
动态申请内存空间,不需要提前申请好内存大小.只要用的时候申请就好.可以动态申请删除内存空间.所有数据的增删比数据灵活.
