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值

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保存元素时的那些事

1. 当发生hash碰撞时，会用新节点与当前位置链表中的每一个节点进行比较

   有相等的（hash相等，equals相等。同一个key），key去重，value覆盖

   不相等，就将新元素的节点添加到链表最后

2. 对于hash碰撞时，当前的hashMap底层，使用的时链表的尾插法

   jdk1.7时，发生hash碰撞，采用的是头插法 （头超法在多线程时会有问题）

3. 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底层有很多的计算都是基于位运算的

1. 通过hash计算元素的存储位置

   jdk早期版本，通过除法取模计算最终的存储位置 hash=101,length=6 , 101%6=5

2. 数组扩容

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种遍历方式 前序遍历，中序遍历，后序遍历

  • 以父节点为基准

    父 左 右 ：前序

    左 父 右 ： 中序

    左 右 父 ： 后续

BST -> AVL -> 红黑树

4 位运算符

运算符都有哪些呢？ 算数运算符 ， 赋值运算符，比较运算符，逻辑运算符，条件运算符，位运算符

位运算符的特点：

• 对二进制进行运算的

• 按位运算的

• 位运算符包括

  • &（按位与），|（按位或），^（按位异或），~（按位取反）

  • <<（左移） , >>（无符号右移） , >>>（带符号右移）