Java基础知识——LInkedList,Iterator,HashMap,HashCode，平衡二叉树红黑树
LinkedLIst 4
Iterator 2
HashMap 构造 属性 构造 put resize
equals,HashCode
平衡二叉树
红黑树：构造 查找 插入 删除
LinkedList源码阅读
知识点一：可以看到LinkedList基于链表，并且是双向循环链表，每一个节点是一个Entry，element，next，previous，构造方法和entry(int index) ，entry(int index) 找index位置的元素并返回。其他的操作比如add,remove都是符合双向循环链表基本操作
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
Entry<E> e = header;
// 根据这个判断决定从哪个方向遍历这个链表
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
// 可以通过header节点向前遍历，说明这个一个循环双向链表，header的previous指向链表的最后一个节点，这也验证了构造方法中对于header节点的前后节点均指向自己的解释
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
}
知识点二“：
expectedModCount字段，
modCount，用于记录对象的修改次数，比如增、删、改
可以理解成version，在特定的操作下需要对version进行检查，适用于Fail-Fast机制。
Fail-Fast 机制
比如当A通过iterator去遍历某集合的过程中，因为iterator长时间拥有对象，而且是线程安全即其他线程也可以操作对象，所以为了防止便利的时候读取脏数据，通过checkForComodification（）方法，判断modCount==expectedModCount，若其他线程修改了此集合，此时会抛出ConcurrentModificationException异常。
知识点三：重写clone方法，利用clone.add(e.element);
public Object clone() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
clone.header = new Entry<E>(null, null, null);
clone.header.next = clone.header.previous = clone.header;
clone.size = 0;
clone.modCount = 0;
for (Entry<E> e = header.next; e != header; e = e.next)
clone.add(e.element);
return clone；
}
知识点四：toArray()
关于赋值
父引用=子对象：上转型对象（子一定拥有父亲的方法）
强转：
直接关系：向下转型
（因为父亲不一定有子的方法）
间接关系：高精度向低精度转型（基本数据类型）
参考资料
不带参数的，返回的是 Object[]
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
//将链表中所有节点的数据都添加到Object[]数组中
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
带参数的：
穿入数组a，如果a能够容纳linkedlist的值，
则0-size-1为linkedlist的值，size为null，size+1-length-1为原值
若不能够容纳，利用反射的方式新建立一个数组并赋值给a
public <T> T[] toArray(T[] a) {
// 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
// 则新建一个T[]数组，T[]的大小为LinkedList大小，并将该T[]赋值给a。
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
//将链表中所有节点的数据都添加到数组a中
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
Iterator:
参考资料
参考资料
知识点一：
接口中的default方法，能够在借口中直接写方法体和抽象类的区别又缩小了
但是如果实现A，B两个接口都有相同函数签名的default的方法，必须重写因为不知道应该继承哪个
如果继承父类A，和实现接口B都有default方法，则会实际为父类A的方法
知识点二：
首先Java提供两个迭代器接口Iterator和ListIterator
Iterator方法比较少：next,hasNext,remove
ListIterator方法比较多：add，previous等等
参考资料
AbstractList：是ArrayList和LinkedList的父类
实现了两个内部类Itr和ListItr
Itr：实现Iterator接口
ListItr：实现ListIterator并且继承自Itr
ArrayList：直接使用AbstractList的Itr
Itr：cursor lastRet(remove时移除此元素)利用数组特性遍历
checkForComodification();
try {
Object next = get(cursor);//先取当前光标所在位置后面的元素
lastRet = cursor++;//然后把最后一次操作所在光标设置成当前光标位置，再把当前光标后移一
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
LinkedList：
单独定义内部类ListItr，它实现了ListIterator接口，用来对LinkedList进行专门迭代，因为LinkedList与ArrayList还不同，它是使用链表结构实现的，所以需专门的迭代器。
ListItr：
lastReturned：最近一次操作返回的元素
Entry next：即将返回的元素
nextIndex：即将返回的元素的编号
public Object next() {
//检查外部是否修改了集合结构，即modCount是否与expectedModCount相等
checkForComodification();
if (nextIndex == size)
throw new NoSuchElementException();
lastReturned = next;//先记录next所在位置，并把它赋给lastReturned
next = next.next;//然后再把next指向下一个元素
nextIndex++;//nextIndex与next操作需同步，所以也要增一
return lastReturned.element;
}
k
HashMap
参考资料
参考资料
前沿：首先HashMap具体实现是由链表+数组的实现方式，并且采用了动态扩容技术
数据结构：
特点：
1：动态扩充
数组是否需要扩充是通过负载因子判断的，如果当前元素个数为数组容量的0.75时，就会扩充数组。这个0.75就是默认的负载因子，可由构造传入。我们也可以设置大于1的负载因子，这样数组就不会扩充，牺牲性能，节省内存。
2：链表和红黑树转化：
为了解决碰撞，数组中的元素是单向链表类型。当链表长度到达一个阈值时（7或8），会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时（6），又会将红黑树转换回单向链表提高性能，这里是一个平衡点。
检查链表长度转换成红黑树之前，还会先检测当前数组数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。所以上面也说了链表长度的阈值是7或8，因为会有一次放弃转换的操作。
3：数据结构是数组+链表
拉链法进行冲突处理
内部类：
继承关系如下：Node是单向链表节点，Entry是双向链表节点，TreeNode是红黑树节点。
Node->Entry->TreeNode
注意Entry是JDK1.7之前的数据机构，1.8后主要是用Node和TreeNode不用Entry可能认为双向循环链表意义不大，效率不如Node
Entry
static class Node<K,V> implements Map.Entry<K,V> {
// hash是经过hash()方法处理过的hashCode，为了使hashCode分布更加随机，
// 待会会深入这个hash()方法。
final int hash;
final K key;
V value;
Node<K,V> next; // 下一个节点
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final int hashCode() {
// key的hashCode异或value的哈希Code
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 其余略
}
HashMap方法：
成员变量
/**
* 数组的默认初始长度，java规定hashMap的数组长度必须是2的次方
* 扩展长度时也是当前长度 << 1。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 数组的最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子，当元素个数超过这个比例则会执行数组扩充操作。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树形化阈值，当链表节点个大于等于TREEIFY_THRESHOLD - 1时，
// 会将该链表换成红黑树。
static final int TREEIFY_THRESHOLD = 8;
// 解除树形化阈值，当链表节点小于等于这个值时，会将红黑树转换成普通的链表。
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树形化的容量，即：当内部数组长度小于64时，不会将链表转化成红黑树，而是优先扩充数组。
static final int MIN_TREEIFY_CAPACITY = 64;
// 这个就是hashMap的内部数组了，而Node则是链表节点对象。
transient Node<K,V>[] table;
// 下面三个容器类成员，作用相同，实际类型为HashMap的内部类KeySet、Values、EntrySet。
// 他们的作用并不是缓存所有的key或者所有的value，内部并没有持有任何元素。
// 而是通过他们内部定义的方法，从三个角度（视图）操作HashMap，更加方便的迭代。
// 关注点分别是键，值，映射。
transient Set<K> keySet; // AbstractMap的成员
transient Collection<V> values; // AbstractMap的成员
transient Set<Map.Entry<K,V>> entrySet;
// 元素个数，注意和内部数组长度区分开来。
transient int size;
// 再上一篇文章中说过，是容器结构的修改次数，fail-fast机制。
transient int modCount;
// 阈值，超过这个值时扩充数组。 threshold = capacity * load factor，具体看上面的静态常量。
int threshold;
// 装在因子，具体看上面的静态常量。
final float loadFactor;
1：构造方法
//主要是对传入的initialCapacity和loadFactor进行参数检验，没有为数组table分配内存空间而是在执行put操作的时候才真正构建table数组
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}
public HashMap(int initialCapacity, float loadFactor)这个构造可以由我们指定数组的初始容量和负载因子。
但是前面说过，数组容量必须是2的次方。所以就需要通过某个算法将我们给的数值转换成2的次方。
tableSizeFor(int cap)就是这个作用。
// 这个方法可以将任意一个整数转换成2的次方。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
0000 0100 0000 0000
0000 0110 0000 0000
0000 0111 1000 0000
0000 0111 1111 1000
0000 0111 1111 1111
0000 1000 0000 0000 可以看到变成2的次方
2：put
检查数组是否为空，执行resize()扩充；
通过hash值计算数组索引，获取该索引位的首节点。
如果首节点为null，直接添加节点到该索引位。
如果首节点不为null，那么有3种情况
① key和首节点的key相同，覆盖value；否则执行②或③
② 如果首节点是红黑树节点（TreeNode），将键值对添加到红黑树。
③ 如果首节点是链表，将键值对添加到链表。添加之后会判断链表长度是否到达TREEIFY_THRESHOLD - 1这个阈值，“尝试”将链表转换成红黑树。
最后判断当前元素个数是否大于threshold，扩充数组。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//tab存放当前的哈希桶，p用作临时链表节点
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前哈希表是空的，代表是初始化
//table为Entry,tab为Node,Entry是Node的子类，上转型对象
if ((tab = table) == null || (n = tab.length) == 0)
//那么直接去扩容哈希表，并且将扩容后的哈希桶长度赋值给n
n = (tab = resize()).length;
//如果当前index的节点是空的，表示没有发生哈希碰撞。直接构建一个新节点Node，挂载在index处即可。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//否则 发生了哈希冲突。
Node<K,V> e; K k;
//如果哈希值相等，key也相等，则是覆盖value操作
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;//将当前节点引用赋值给e
else if (p instance of TreeNode)//如果是红黑树节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//不是红黑树节点
//遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍历到尾部，，仍没有key与其相等，说明是新节点，追加新节点到尾部
p.next = newNode(hash, key, value, null);
//如果追加节点后，链表数量>=8，则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果找到key与其相同，说明是曾经插入过的节点
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不是null，说明有需要覆盖的节点，由上面的break;弹出
if (e != null) { // existing mapping for key
//则覆盖节点值，并返回原oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这是一个空实现的函数，用作LinkedHashMap重写使用。
afterNodeAccess(e);
return oldValue;
}
}
//如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。
++modCount;
//更新size，并判断是否需要扩容。
if (++size > threshold)
resize();
//这是一个空实现的函数，用作LinkedHashMap重写使用。
afterNodeInsertion(evict);
return null;
}
计算实际存储位置：
1：利用Java重写的HashCode计算哈希值
2：对哈希值进行扰动处理 (h = key.hashCode()) ^ (h >>> 16)
3：与运算代替模计算(n - 1) & hash
hash()：转为hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashCode的高16位与低16位进行异或运算注意h进行h >>> 16已经被赋值，因为内部数组的容量一般都不会很大，基本分布在16~256之间。所以一个32位的hashCode，一直都用最低的4到8位进行与运算，而高位几乎没有参与。“扰动函数”
获得索引值：
(p = tab[i = (n - 1) & hash]) == null
(n - 1) & hash实际上=hash%(n)n是长度，为一个2的次方数
利用与运算代替模运算可以极大增加运算速度
Hash表扩容：
1：计算新数组的容量和阈值
2：将原数组的元素拷贝到新数组中
这里JDK1.7之前利用的是重新计算Hash索引，即rehash操作
1.8后，由于数组容量是2的次方且扩充后翻倍，则只需要判断原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”
final HashMap.Node<K,V>[] resize() {
HashMap.Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果数组已经是最大长度，不进行扩充。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则数组容量扩充一倍。（2的N次方）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果数组还没创建，但是已经指定了threshold（这种情况是带参构造创建的对象），threshold的值为数组长度
// 在 "构造函数" 那块内容进行过说明。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 这种情况是通过无参构造创建的对象
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 可能是上面newThr = oldThr << 1时，最高位被移除了，变为0。
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 到了这里，新的数组长度已经被计算出来，创建一个新的数组。
@SuppressWarnings({"rawtypes","unchecked"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
// 下面代码是将原来数组的元素转移到新数组中。问题在于，数组长度发生变化。
// 那么通过hash%数组长度计算的索引也将和原来的不同。
// jdk 1.7中是通过重新计算每个元素的索引，重新存入新的数组，称为rehash操作。
// 这也是hashMap无序性的原因之一。而现在jdk 1.8对此做了优化，非常的巧妙。
if (oldTab != null) {
// 遍历原数组
for (int j = 0; j < oldCap; ++j) {
// 取出首节点
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果链表只有一个节点，那么直接重新计算索引存入新数组。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果该节点是红黑树，执行split方法，和链表类似的处理。
else if (e instanceof HashMap.TreeNode)
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 此时节点是链表
else { // preserve order
// loHead，loTail为原链表的节点，索引不变。
HashMap.Node<K,V> loHead = null, loTail = null;
// hiHeadm, hiTail为新链表节点，原索引 + 原数组长度。
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;
// 遍历链表
do {
next = e.next;
// 新增bit为0的节点，存入原链表。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 新增bit为1的节点，存入新链表。
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原链表存回原索引位
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 新链表存到：原索引位 + 原数组长度
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
关键点：为什么实际大小总是2的幂？
我的理解：
原因一：
因为index=hash%length-1
比如对于：
length=16 则length-1 =15 即 00001111
length=32 则length-1=31 即 00011111
可以看到，对于一个相同的hash，分别&两个不同的length-1，得到的结果result1,result2 差别就只在右数第5位，相当于扩容后只要修改一位就可以改变索引
原因二:
因为length=2^n，则length-1的位都是保持00001111111的形状，而hash&length-1中，高位不会产生影响，而低位任意一个变化变化都会产生影响，减少冲突的概率。
在h<length的情况下：
对于长度：23 length-1则比特为 10110，则对于结果result=10110
既可以是h=11110 10110 11111 10111 都对应相同的结果冲突增加
而对于长度32 length-1 则比特位11111 ，则对于结果10110
只有h=10110才可以与其对应
原因三：可以用与运算代替模运算，增加了效率
Object中有两个特殊方法HashCode()和equals()
关于HashCode()；
参考资料
不同基本数据类型的HashCode()不一样，并且一般都重写了方法
例如String
public int hashCode() {
int h = hash;
int len = count;
if (h == 0 && len > 0) {
int off = offset;
char val[] = value;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
例子：
输入abcd
// 第一步 = (int)‘a’
// 第二步 = (31 * (int)‘a’) + (int)‘b’
// 第三步 = 31 * ((31 * (int)‘a’) + (int)‘b’) + (int)'c
// 第四步 = 31 * (31 * ((31 * (int)‘a’) + (int)‘b’) + (int)‘c’) + (int)‘d’
// 第五步 = 31 * (31 * (31 * ((31 * (int)‘a’) + (int)‘b’) + (int)‘c’) + (int)‘d’) + (int)‘e’
也就abcd的hashcode值为，a31^ 4+b31^ 3+c31^ 2+d31^ 1+e*31^0
特点：
1：public native int hashCode();
说明是一个本地方法，它的实现是根据本地机器相关的
当然我们在实现的时候可以写成java，只是要注意一点就是不同机器同一对象得到HashCode不同可能是溢出处理不一样？
2：不可逆
之所以选择值31是因为它是奇数素数。如果它是偶数，并且乘法溢出，则信息将丢失，因为2的乘法相当于移位。、31的一个很好的特性是，可以用一个移位和一个减法来代替乘法，以获得更好的性能：31×i =（i < 5）- i
3： if (h == 0 && len > 0) 如果h不等于0说明之前计算过，直接返回可能和equals也有关
在String中有一个私有实例字段hash表示该串的哈希值，在第一次调用hashCode方法时，字符串的哈希值被计算并且赋值给hash字段。之后再调用hashCode方法便可以直接取hash字段返回。
equals
参考资料
public boolean equals(Object obj) {
return (this == obj);
}
很明显是对两个对象的地址值进行的比较（即比较引用是否相同）。
但是String 、Math、Integer、Double等这些封装类在使用equals()方法时，已经覆盖了object类的equals()方法。
String重写了此方法，原因在于String对象可能存储在堆上，也可能存储在本地方法区上，但是我们实际想比较的是值是否相同
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) {
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
while (n– != 0) {
if (v1[i++] != v2[j++])
return false;
}
return true;
}
}
return false;
}
需要注意的是当equals()方法被override时，hashCode()也要被override。按照一般hashCode()方法的实现来说，相等的对象，它们的hash code一定相等。
1、相等（相同）的对象必须具有相等的哈希码（或者散列码）。
2、如果两个对象的hashCode相同，它们并不一定相同。
红黑树：
参考资料
性质：
1：根节点和叶子结点是黑色
2：不能出现连续的两个红色结点
3：从根到任意叶子结点上的黑色结点数相同
查找：O(log2(N))的时间复杂度
插入：
判断父亲节点
1：若是黑色，直接插入红色节点
2：若是红色，判断叔叔节点。插入红色节点后
若叔叔节点是红色：交换色（父叔节点和祖父节点换色）
若叔叔节点是黑色（或者不存在）：交换色+旋转 四种情况
删除：
叶子节点：直接删除
有一个叶子：找子节点的最邻近节点作为替换节点
有两个叶子：仍然找子节点的最邻近作为替换节点（一般是右子树）
若替换兄弟节点在右子树
替换节点红色：直接替换并改为被删节点色
替换节点黑色：
1 替换兄弟节点为红色：换色+旋转
2 替换兄弟节点是黑色：
2.1兄弟节点的右子节点为红色：改色+旋转
2.2兄弟节点的右子为黑色，但是左子为红色：换色后旋转——变为2.1
2.3兄弟节点双子都是黑色：改色+父节点作为替换节点
优势：
平衡二叉树的插入/删除操作带来的旋转操作可能会达到logn次，而红黑树的插入/删除操作带来的旋转操作最多为2/3次。
平衡二叉树的删除：
参考资料
左子树上节点的删除相当于我们在右子树上插入了一个新节点，右子树上节点的删除相当于在左子树上插入了一个新节点
三种情况：
1：被删节点为叶节点
2：被删节点只一个叶节点
3：被删节点有两个叶子结点
上一篇： Raspberry Pi 3B学习笔记