JAVA基础：HashMap底层数组容量控制，TreeMap底层存取机制，位运算符，原码反码补码

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值

java">public boolean add(E e) {return map.put(e, PRESENT)==null;
}

TreeSet

TreeSet底层是通过TreeMap集合存储。
存储的key是自然有序的（有大小顺序）
集合存储的类对象的，这就要求存入TreeSet中的元素（TreeMap中的key），要可以比较大小

自身比较(Comparable)，或提供第三方比较器(Comparator)
使用无参构造器创建TreeSet时，要求存储的元素必须自身可以比较

要么就使用可以传递第三方比较器的Tree构造方法

java">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的次幂数

java">//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结构，适合快存，快取
区别
1. Hashtable早期版本，线程同步，安全性高，效率低
  
  HashMap，非线程同步，安全性低，效率高
2. Hashtable中的key和value不能为null
  
  HashMap中的key和value可以为null

TreeMap

底层使用的是红黑树存储元素，是BST树的一种特殊形式
我们暂时只需要了解BST
- 是一个二叉树，一个节点有左右两个子节点，和一个父节点
- 节点间存储在大小关系，左枝节点 < 父节点 < 右枝节点
存储
- 第一个节点必然就是最开始的节点，我们称为根节点
- 第二个数据添加时，会从根节点开始，依次进行大小比较
  - 如果与根节点key相同，说明重复，key取重，value覆盖
  - 如果与根节点key不相同，根据大小，如果小于根节点的key，向左枝找位置，否则反之
  - 接着会与左枝节点比较，相等取重，不等继续比较大小
  - 直到某一个节点的左枝或右枝为null，说明找到了要存放的位置，完成节点链接即可。
遍历
- 二叉树有3种遍历方式前序遍历，中序遍历，后序遍历
- 以父节点为基准
  
  父左右：前序
  
  左父右：中序
  
  左右父：后续