List常用实现类
-
List集合常用的实现类有3个 ， ArrayList , LinkedList , Vector
ArrayList
-
类似于我们之前的ArrayBox
-
底层使用数组存储元素， 插入删除的效率低，检索的效率高
-
当底层数组存储容量不足时，会进行扩容，每次扩容都是原数组的1.5倍
-
使用无参构造器创建ArrayList集合时，首先提供的是一个默认0长度的数组（防止内存资源浪费）
第一次add元素的时候，会创建一个10个长度的数组
Vector
-
我们在开发中已经不怎么使用了
-
Vector是ArrayList早期版本1.0
-
起初有自己的一套api方法，后来与ArrayList实现了相同的List接口
-
Vector也是使用数组的结构存储
-
Vector早期版本，线程同步的，安全性高，但效率低。
ArrayList是非线程同步的，安全性低，但效率高
(想到StringBuilder和StringBuffer)
-
Vector底层数组容量不足时，会按照原容量的2倍扩容
ArrayList按照原容量1.5扩容
-
Vector在创建对象时，可以指定扩容增量，每次扩容时会按照指定的增量扩容
ArrayList只能1.5倍扩容
LinkedList
-
类似于我们之前封装的LinkedBox
-
底层使用双向链表存储元素，插入删除效率高，检索效率低
-
LinkedList还提供了一组与头尾元素操作相关的方法。
2 Set常用实现类
-
常用的实现类有2个 ， HashSet ， TreeSet
-
底层用来存储元素的都是对应的Map，相当于只存储了map中的key，而没有value
HashSet
-
底层使用的是HashMap存储
-
向set中存储一个元素，就相当于向map中存储了一个key
-
这个value是什么呢？
-
是 null 么。 不是 。 底层的map，如果key重复，会返回之前的value。 如果key不重复，返回null
对于set而言，返回null，说明key不重复，说明保存成功。
反之说明key重复，保存失败
如果用null作为value，就无法判断保存是否成功
-
需要让value值是一个具体的对象。 但每次创建一个新对象，又浪费空间。所以用唯一的对象作为value值
-
public boolean add(E e) {return map.put(e, PRESENT)==null;
}
TreeSet
-
TreeSet底层是通过TreeMap集合存储。
-
存储的key是自然有序的（有大小顺序）
-
集合存储的类对象的，这就要求存入TreeSet中的元素（TreeMap中的key），要可以比较大小
自身比较(Comparable)，或提供第三方比较器(Comparator)
-
使用无参构造器创建TreeSet时，要求存储的元素必须自身可以比较
要么就使用可以传递第三方比较器的Tree构造方法
public TreeSet(Comparator comparator){}-
TreeSet在存储第一个元素的时候，也需要保证元素是可以比较大小的。
3 Map常用实现类
-
Map常用的实现类有3个， HashMap ，TreeMap ， Hashtable
HashMap
-
底层使用数组 + 链表结构存储元素。jdk1.8之后，变成了数组 + 链表 or 红黑树 存储元素
-
hash的存储特点是单一元素的 快存 和 快取
-
每次存储的元素（key），都会通过一个hash算法，计算出该元素在数组中存储的位置
有可能第1个元素，被计算出存储在5位置。 第2个元素，被计算出存储2位置。使得存储位置是零散的
-
是根据元素的什么信息进行位置的hash计算
是根据元素的hashcode值。 每一个元素都会有一个hashcode值，我们通过调用hashcode方法来获得。
Object中有一个hashcode方法，是一个native修饰的方法，表示该方法是由jvm（c/c++）语言实现的
是由jvm为对象提供的一个尽可能唯一的数值。可以当成地址使用，不是内存地址
对象的hashcode不是与生俱来的，当第一次调用hashcode方法时，才会生成hashcode（JOL验证）
hashcode值的作用，就是为hash存储结构来计算存储位置的。
hashcode方法可以被重写，重写原则是， equals相等， hashcode也相等。反之无所谓。
-
hash碰撞 ？ 两个不同的对象，通过hash计算后，算出了相同的存储位置
两个对象都需要存储，会在当前位置形成一个链表
扩展：hashmap保存元素时的那些事
-
当发生hash碰撞时，会用新节点与当前位置链表中的每一个节点进行比较
有相等的（hash相等，equals相等。同一个key），key去重，value覆盖
不相等，就将新元素的节点添加到链表最后
-
对于hash碰撞时，当前的hashMap底层，使用的时链表的尾插法
jdk1.7时，发生hash碰撞，采用的是头插法 （头超法在多线程时会有问题）
-
jdk1.8之后，HashMap底层使用数组 + 链表 或 红黑树。为什么用到树呢？
防止链表过长，影响hash效率。当链表长度超过8时，就会尝试转换成红黑树了。
如果数组长度<64 , 会优先2倍扩容
如果数组长度>64，就会实现链表到红黑树的转化
HashMap底层数组的长度问题
-
尽管HashMap提供了有参构造器，可以指定数组的初始容量，但最终都会处理成的2的次幂
-
也就是说， hashmap底层的数组，无论如何其长度都是2的次幂数
//cap = 10
static final int tableSizeFor(int cap) {//n = 9//16个0 1000 0000 0000 0000int n = cap - 1;//n = n | n>>>1 ;//n = 28个0 1001 | 28个0 0100//n = 28个0 1101//1000 0101 0010 1001 | 0100 0010 1001 0100//1100 0111 1011 1101n |= n >>> 1;//1101 | 0011//28个0 1111 == 10000=16//11111== 100000=32//1100 0111 1011 1101 | 0011 0001 1110 1111//1111 0111 1111 1111n |= n >>> 2;// 1111 | 0000//1111 0111 1111 1111 | 0000 1111 0111 1111 n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;//x个0， y个1return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
hashmap底层有很多的计算都是基于位运算的
-
通过hash计算元素的存储位置
jdk早期版本，通过除法取模计算最终的存储位置 hash=101,length=6 , 101%6=5
-
数组扩容
Hashtable
-
Hashtable 与HashMap作用相同，也是hash结构，适合快存， 快取
-
区别
-
Hashtable早期版本，线程同步，安全性高，效率低
HashMap，非线程同步，安全性低，效率高
-
Hashtable中的key和value不能为null
HashMap中的key和value可以为null
-
TreeMap
-
底层使用的是红黑树存储元素，是BST树的一种特殊形式
-
我们暂时只需要了解BST
-
是一个二叉树，一个节点有左右两个子节点，和一个父节点
-
节点间存储在大小关系，左枝节点 < 父节点 < 右枝节点
-
-
存储
-
第一个节点必然就是最开始的节点，我们称为根节点
-
第二个数据添加时，会从根节点开始，依次进行大小比较
-
如果与根节点key相同，说明重复，key取重，value覆盖
-
如果与根节点key不相同，根据大小，如果小于根节点的key，向左枝找位置，否则反之
-
接着会与左枝节点比较，相等取重，不等继续比较大小
-
直到某一个节点的左枝或右枝为null，说明找到了要存放的位置，完成节点链接即可。
-
-
-
遍历
-
二叉树有3种遍历方式 前序遍历，中序遍历，后序遍历
-
以父节点为基准
父 左 右 ：前序
左 父 右 ： 中序
左 右 父 ： 后续
-
BST -> AVL -> 红黑树
4 位运算符
运算符都有哪些呢？ 算数运算符 ， 赋值运算符，比较运算符，逻辑运算符，条件运算符，位运算符
位运算符的特点：
-
对二进制进行运算的
-
按位运算的
-
位运算符包括
-
&（按位与），|（按位或），^（按位异或），~（按位取反）
-
<<（左移） , >>（无符号右移） , >>>（带符号右移）
-