数据结构
2021-09-06 21:45:42 0 举报AI智能生成
数据结构
作者其他创作
大纲/内容
HashMap
内部结构
1.7
数组+链表
1.8
数组+链表/红黑树
更新原因?
防止发生hash冲突，链表长度过长，将时间复杂度由`O(n)`降为`O(logn)`;
转红黑树
容量>=64 且 单个位置链表长度>=8
putVal() TreeifyBin()
转链表
单个位置链表长度<=6 将红黑树转化会链表
split()
这两个阈值如何确定的
因为经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，概率说话。。因为8够用了，
至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生。
至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生。
hashmap的13 个成员变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;-> 数组默认初始容量：16
static final int MAXIMUM_CAPACITY = 1 << 30;-> 数组最大容量2 ^ 30 次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;-> 默认负载因子的大小：0.75
static final int MIN_TREEIFY_CAPACITY = 64;-> 树形最小容量：哈希表的最小树形化容量,超过此值允许表中桶转化成红黑树
static final int TREEIFY_THRESHOLD = 8;-> 树形阈值：当链表长度达到8时，将链表转化为红黑树
static final int UNTREEIFY_THRESHOLD = 6;-> 树形阈值：当链表长度小于6时，将红黑树转化为链表
transient int modCount; -> hashmap修改次数
int threshold; -> 可存储key-value 键值对的临界值 需要扩充时;值 = 容量 * 加载因子
transient int size; 已存储key-value 键值对数量
final float loadFactor; -> 负载因子
transient Set< Map.Entry< K,V >> entrySet; -> 缓存的键值对集合
transient Node< K,V>[] table; -> 链表数组（用于存储hashmap的数据）
static final int MAXIMUM_CAPACITY = 1 << 30;-> 数组最大容量2 ^ 30 次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;-> 默认负载因子的大小：0.75
static final int MIN_TREEIFY_CAPACITY = 64;-> 树形最小容量：哈希表的最小树形化容量,超过此值允许表中桶转化成红黑树
static final int TREEIFY_THRESHOLD = 8;-> 树形阈值：当链表长度达到8时，将链表转化为红黑树
static final int UNTREEIFY_THRESHOLD = 6;-> 树形阈值：当链表长度小于6时，将红黑树转化为链表
transient int modCount; -> hashmap修改次数
int threshold; -> 可存储key-value 键值对的临界值 需要扩充时;值 = 容量 * 加载因子
transient int size; 已存储key-value 键值对数量
final float loadFactor; -> 负载因子
transient Set< Map.Entry< K,V >> entrySet; -> 缓存的键值对集合
transient Node< K,V>[] table; -> 链表数组（用于存储hashmap的数据）
构造方法
HashMap的初始容量大小
默认大小是16，负载因子是0.75，
如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方，例如如果传10，大小为16
tableSizeFor()
通过将传入的值不断>>>1,2,4,8,16 位并且和自己或, 然后原本最高位的1后面的位数全部变为1,
这样+1之后就只有比原来的最高的一个位置是1其他都是0, 这样就是一个比原来位置大的2的整数次方了
这样+1之后就只有比原来的最高的一个位置是1其他都是0, 这样就是一个比原来位置大的2的整数次方了
(n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
hash()
计算key的hash值
hash函数是先拿到 key 的hashcode，是一个32位的int值，然后让hashcode的高16位和低16位进行异或操作。
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
所以key是null的时候自动分配到了数组的第一个位置
为什么这样计算?
右移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。
而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
我们希望扰动函数尽可能降低hash碰撞，越分散越好；直接使用key的hashCode()函数返回int整型的范围, 冲突少但是范围太大, 而我们的数组长度没有这么大, 一开始才16
bit操作效率也很高
indexFor()
根据key的hash值计算数组中的位置
扩容位置不变或索引+旧容量大小；
h & (length-1)
位运算效率高, 比取余运算快
因为数组的长度一定是2的整数次方 , 所以二进制只有一个位置为1, 这个长度-1后, 高位的1变成0,剩下的位置全部是1,
这样那这个hash按位与运算一定得到一个在长度范围内的下标,
这样那这个hash按位与运算一定得到一个在长度范围内的下标,
同时, 当数组扩容以后, n变成两倍就是最高位左移了一位, n-1相比之前只在最高位多了一个1, 所以如果这个key之前的hash值在扩容后的最高位是1, 那么起始就是在原来的基础上加了一个原数组的大小, 因为原来的地位运算结果还是一样的
put
插入过程
判断数组是否为空，为空进行初始化;
(tab = table) == null || (n = tab.length) == 0
不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
(p = tab[i = (n - 1) & hash]) == null
查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
(p = tab[i = (n - 1) & hash]) == null
存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
判断hash相等, 可能key都是null, 不是null的情况下需要用equals判断相等
如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；
p instanceof TreeNode
是树形结点, 说明已经是红黑树, 插入红黑树
putTreeVal
如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于等于8并且数组长度大于等于64， 大于的话链表转换为红黑树；
p.next = newNode(hash, key, value, null);
遍历到链表尾没有发现相同key的结点需要插入新节点
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
treeifyBin(tab, hash);
判断插入之前的结点数量是否>=7, 因为插入的这个结点数量还没算在内
在一个for死循环loop里面找到合适的位置插入或者替换, 所以bincount记录当前链表结点是第几个, 插入前是7个插入了新结点就是8个了, 就需要扩容了
treeifyBin方法, 判断数组长度是否<64 小于就不进行转换
split方法中 <=6 就转换回链表
插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。
if (++size > threshold)
resize();
resize();
Get
不存在返回null, 存在, 在链表或者红黑树中查找对应的key.equals的值
resize()
初始化, 如果数组为空, 或者根据传入的参数, 找到2的整数次方作为长度,
需要扩容的情况, 根据hash决定是否不动还是移动一个之前数组大小的位置
需要扩容的情况, 根据hash决定是否不动还是移动一个之前数组大小的位置
1.8HashMap的优化
底层实现
1.7
数组+链表
1.8
数组+链表或红黑树
防止发生hash冲突，链表长度过长，将时间复杂度由`O(n)`降为`O(logn)`;
新节点插入链表位置
1.7
头插法
多线程产生环
假设有T1，T2两个线程同时对一个HashMap进行put操作，刚好，HashMap达到了扩容的条件，
这是两个线程都会去对这个HashMap进行扩容
链表A-->B，假设A B扩容后，计算的index依然相同，那么他们还会存放在同一链表中
这是两个线程都会去对这个HashMap进行扩容
链表A-->B，假设A B扩容后，计算的index依然相同，那么他们还会存放在同一链表中
假设当T1线程进入到transfer时，先会拿到A，Entry<K,V> next = e.next拿到B，这时T1线程被挂起。
T2线程进入transfer时，先会拿到A，Entry<K,V> next = e.next拿到B，然后向下执行，将A放入index，
之后循环至B，B继续执行插入链表头，就会将B.next->A,
之后循环至B，B继续执行插入链表头，就会将B.next->A,
T2线程执行完之后，T1继续执行，将A又插入链表头导致了A.next = B，循环至B, 此时B的next指向A（T2做了全局的修改），
这样就导致了产生环一直不断的循环下去, 原因在于头插法改变了原有结点的指针指向关系, 所以多线程产生环
1.8
尾插法
不产生环
尾插法不会改变原有的next指向关系，所以他不会出现环
扩容元素的移动方式
1.7
对原数组中的元素进行重新hash定位在新数组的位置，
1.8
位置不变或索引+旧容量大小；
1. 这是由于扩容是扩大为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1，怎么理解呢？
2. 扩容前长度为16，用于计算(n-1) & hash 的二进制n-1为0000 1111，扩容为32后的二进制就高位多了1，为0001 1111。
3. 因为是& 运算，1和任何数 & 都是它本身，那就分二种情况，如下图：原数据hashcode高位第4位为0和高位为1的情况；
4. 第四位高位为0，重新hash数值不变，第四位为1，重新hash数值比原来大16（旧数组的容量）
2. 扩容前长度为16，用于计算(n-1) & hash 的二进制n-1为0000 1111，扩容为32后的二进制就高位多了1，为0001 1111。
3. 因为是& 运算，1和任何数 & 都是它本身，那就分二种情况，如下图：原数据hashcode高位第4位为0和高位为1的情况；
4. 第四位高位为0，重新hash数值不变，第四位为1，重新hash数值比原来大16（旧数组的容量）
插入元素与判断扩容的顺序
1.7
先判断是否需要扩容，再插入
1.8
先进行插入，插入完成再判断是否需要扩容；
个人观点, 多了链表转换红黑树的步骤, 所以如果之前判断, 而插入后刚好达到了阈值, 就没办法进行转化, 只有下一次插入才会转换
HashMap的线程安全性
不安全
数据覆盖问题
当A线程判断index位置为空后正好挂起，B线程开始往index位置写入数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；
同时扩容
putVal方法执行完插入判断是否需要扩容, 这时候存在两个线程同时判断都需要扩容库容了两次 (++size)
怎么解决HashMap线程不安全的问题
Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。
HashTable
操作方法上加synchronized关键字，锁住整个数组，粒度比较大，
Collections.synchronizedMap
使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；
ConcurrentHashMap
使用分段锁，降低了锁粒度，让并发度大大提高。
成员变量使用volatile 修饰，免除了指令重排序，同时保证内存可见性
使用CAS操作和synchronized结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。
HashMap的总结
hashmap基于哈希表的 map接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。
底层实现, 数组+链表/红黑树, 默认初始大小16, 默认负载因子0.75f
新结点插入链表的尾部
当链表结点个数>=8并且数组结点个数>=64 需要转化成红黑树, 红黑树结点个数<=6需要转换回链表
数组结点个数>数组大小*负载因子 需要将数组大小扩容为原来的2倍, 结点位置可能不变或者+原数组大小的位置
ConcurrentHashMap
底层实现
1.7
Segment 数组结构和 HashEntry 数组结构组成
哈希桶数组切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。
Segment
内部类, 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。Segment 默认为 16，也就是并发度为 16。
HashEntry
存放元素, 静态内部类
volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下数据获取时的可见性！
1.8
Node数组+链表+红黑树结构
采用CAS + synchronized实现更加细粒度的锁。
将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度
cas 体现在结点位置没有元素, 通过CAS将其放在对应的位置上
synchronized 体现在 put操作 synchronized代码块将对应位置头结点当做锁对插入操作加锁
为什么使用内置锁 synchronized替换 可重入锁 ReentrantLock
synchronized 锁的实现引入了大量的优化，
并且 synchronized 有锁升级过程，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
减少内存开销
使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS 来获得同步支持
并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
put()
1.7
首先会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
1.8
1. 根据 key 计算出 hash 值；
2. 判断是否需要进行初始化；
3. 定位到 Node，拿到首节点 f，判断首节点 f：
1. 如果为 null ，则通过 CAS 的方式尝试添加；
2. 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容；
3. 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入；
4. 当在链表长度达到 8 的时候，数组扩容或者将链表转换为红黑树。
2. 判断是否需要进行初始化；
3. 定位到 Node，拿到首节点 f，判断首节点 f：
1. 如果为 null ，则通过 CAS 的方式尝试添加；
2. 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容；
3. 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入；
4. 当在链表长度达到 8 的时候，数组扩容或者将链表转换为红黑树。
get()
1.7
根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，
由于 HashEntry 涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以每次获取时都是最新值。
由于 HashEntry 涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以每次获取时都是最新值。
1.8
1. 根据 key 计算出 hash 值，判断数组是否为空；
2. 如果是首节点，就直接返回；
3. 如果是红黑树结构，就从红黑树里面查询；
4. 如果是链表结构，循环遍历判断。
2. 如果是首节点，就直接返回；
3. 如果是红黑树结构，就从红黑树里面查询；
4. 如果是链表结构，循环遍历判断。
是否需要加锁?
get 方法不需要加锁。因为 Node 的元素 value 和指针 next 是用 volatile 修饰的，
在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。
在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。
哈希桶数组table用 volatile 修饰主要是保证在数组扩容的时候保证可见性。和get方法不需要加锁无关
不支持 key 或者 value 为 null 的原因
put操作会判断 key==null value==null 并且抛出空指针异常
因为 ConcurrentHashMap 是用于多线程的 ，如果ConcurrentHashMap.get(key)得到了 null ，这就无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，就有了二义性。
而用于单线程状态的 HashMap 却可以用containsKey(key) 去判断到底是否包含了这个 null 。
反证法
A线程get(key)=null, 现在不缺定这个key是否对应的val=null 还是不存在这个key
如果预期不存在这个key, A线程通过containsKey(key), 判断这个key是否存在, 应该返回false
但是如果在A线程get(key)以后B线程插入了这个key, A线程之后判断就为true, 与真实情况不符合
并发度
1.7
Segment[]的数组长度，默认是16
1.8
Node数组的大小, 一把锁只会锁住数组的一个位置
JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别
- 数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
- 保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+synchronized保证线程安全。
- 锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。
- 链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量大于 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。
- 查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。
- 保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+synchronized保证线程安全。
- 锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。
- 链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量大于 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。
- 查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。
HashMap vs 其他Map
HashMap vs CourrentHashMap
数据结构
数组+链表/红黑树
线程安全
HashMap
线程不安全
ConcurrentMap
如何保证线程安全
JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock
JDK1.8 采用CAS+synchronized保证线程安全
锁的粒度
JDK1.7 是对需要进行数据操作的 Segment 加锁
JDK1.8 调整为对每个数组元素加锁（Node）。
TreeMap
介绍
有序key-value集合
通过红黑树实现
根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序
TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。
红黑树
属性
- 1. 每个节点都只能是红色或者黑色
- 2. 根节点是黑色
- 3. 每个叶节点（NIL节点，空节点）是黑色的。
- 4. 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
- 5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 2. 根节点是黑色
- 3. 每个叶节点（NIL节点，空节点）是黑色的。
- 4. 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
- 5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
约束
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的
put
构建排序二叉树
1. 以根节点为初始节点进行检索。
2. 与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。
3. 循环递归2步骤知道检索出合适的叶子节点为止。
4. 将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。
2. 与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。
3. 循环递归2步骤知道检索出合适的叶子节点为止。
4. 将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。
平衡二叉树
fixAfterInsertion(e);
左旋：rotateLeft()
就是将新增节点（N）当做其父节点（P），将其父节点P当做新增节点（N）的左子节点。即：G.left ---> N ,N.left ---> P。
右旋：rotateRight()
P.right ---> G. G.parent ---> P。
着色：setColor()
在红黑树中，它是依靠节点的颜色来维持平衡的。
delete()
找到删除结点左子树的最右结点 或者 右子树的最左结点代替这个待删除的结点, 然后删除选择代替的结点
无子节点（红色节点）
对该节点直接删除即可，不会影响树的结构
该节点为叶子节点它不可能存在子节点-----如子节点为黑，则违反黑节点数原则
有一个子节点
用子节点替代待删除节点，然后删除子节点即可
有两个子节点
需要找到一个替代待删除节点（N）来替代它，然后删除N即可
LinkedHashMap
HashMap+双向链表
将所有Entry节点链入一个双向链表的HashMap
LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性
额外维护了一个双向链表用于保持迭代顺序。此外，LinkedHashMap可以很好的支持LRU算法
HashMap vs Hashtable
作者不同
HashMap
Hashtable
继承父类不同
都实现了Map、Cloneable、Serializable三个接口。
HashMap继承自抽象类AbstractMap
HashTable继承自抽象类Dictionary。其中Dictionary类是一个已经被废弃的类
对外接口不同
Hashtable比HashMap多提供了elments() 和contains() 两个方法。
elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。
contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法
对Null key 和Null value的支持不同
HashMap
null可以作为键，这样的键只有一个, 存放在数组第一个位置
可以有一个或多个键所对应的值为null。
可以有一个或多个键所对应的值为null。
- 当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。
- 因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
- 因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
Hashtable
既不支持Null key也不支持Null value
- 当key为Null时，调用put() 方法，key.hashCode()会报空指针异常
- 当value为null值时，put()方法先判断value==null 直接报空指针异常
- 当value为null值时，put()方法先判断value==null 直接报空指针异常
线程安全
HashMap
HashMap不是线程安全的，在多线程并发的环境下，可能会产生死锁等问题。使用HashMap时就必须要自己增加同步处理，
Hashtable
Hashtable是线程安全的，它的每个方法中都加入了Synchronize方法。
遍历方式的内部实现上不同
Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。
HashMap
HashMap的Iterator是fail-fast迭代器。当有其它线程改变了HashMap的结构（增加，删除，修改元素），将会抛出ConcurrentModificationException。
不过，通过Iterator的remove()方法移除元素则不会抛出ConcurrentModificationException异常
Hashtable
JDK8之前的版本中，Hashtable是没有fast-fail机制的。在JDK8及以后的版本中 ，HashTable也是使用fast-fail的
modCount
modcount可以理解为是当前hashtable的状态。每发生一次操作，状态就向前走一步。设置这个状态，主要是由于hashtable等容器类在迭代时，判断数据是否过时时使用的。
初始容量和每次扩充容量大小
HashMap
默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
Hashtable
默认的初始大小为11，之后每次扩充，容量变为原来的2n+1
创建时，如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。
计算hash值的方法
为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。
HashTable
对象的hashCode 除以数组长度的余数得到在数组的位置
HashMap
HashMap为了提高计算效率，将哈希表的大小设为2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。
HashMap通过扰动函数将高16位和低16异或 得到hash值
HashSet vs TreeSet
底层实现
HashSet
底层实现 HashMap key是存入的元素, val都是 static final new Object()
TreeSet
底层实现基于 TreeMap实现 TreeMap底层实现是红黑树, 所以TreeSet可以实现排序
元素是否有序
HashSet
元素是无序的,
因为存入底层HashMap是通过存入元素的hashcode()找到放入HashMap的位置
TreeSet
集合元素有序 因为底层基于TreeMap实现
null值的支持
HashSet
集合元素有且只能有一个null值, 并且放在底层HashMap的第一个Entry位置,
因为HashMap.hash()会判断key是否是null, 如果是null就会返回hash=0
TreeSet
集合元素不能有null值, 因为底层TreeMap.put()方法遇到key=null 会出现空指针异常
线程安全
都不是线程安全的
为什么集合元素不重复
HashSet
因为底层基于HashMap, 根据hashcode决定放在底层数组的哪个位置, 重合的元素(key)equals方法相等,
那么put方法会覆盖两个相等的元素, 保证不存在重复元素
那么put方法会覆盖两个相等的元素, 保证不存在重复元素
TreeSet
同理
add()
HashSet
key是加入set的元素, val是一个静态不可变的Object对象, 通过底层的hashMap的put方法加入
TreeSet
通过底层TreeMap的put方法实现
contains()
调用底层Map的containsKey()
ArrayList vs LinkedList vs Vector
Arraylist与 LinkedList
线程安全
都不是线程安全的
底层实现
Arraylist 底层使用的是Object数组
LinkedList 底层使用的是双向链表数据结构；
插入删除
ArrayList
但是如果要在指定位置 i 插入和删除元素的话（`add(int index, E element)`）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作
LinkedList
LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）
查看对应下标位置的值, 比较从链表头或者尾更快的方式查询 node(index)方法
快速访问
快速随机访问就是通过元素的序号快速获取元素对象(对应于`get(int index)`方法)。
ArrayList 实现了RandmoAccess 接口，有随机访问功能。
LinkedList 不支持高效的随机元素访问，
内存空间占用
ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间
LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
ArrayList 与 Vector
Vector是线程安全的，ArrayList不是线程安全的。其中，Vector在关键性的方法前面都加了synchronized关键字，来保证线程的安全性
ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍，
Array 和 ArrayList
- Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
- Array 大小是固定的，ArrayList 的大小是动态变化的。
- ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等。
- Array 大小是固定的，ArrayList 的大小是动态变化的。
- ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等。
ArrayList 的扩容机制
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原容量的1.5倍
添加一个元素的时候, 数组大小变为10, 不插入元素一直是空数组,
过程
判断是否可以容纳e，若能，则直接添加在末尾；若不能，则进行扩容，然后再把e添加在末尾
每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力，经过处理之后将元素存储在数组elementData的尾部
HashCode vs Equals
== 和 equals 的区别是什么
==
它的作用是判断两个对象的地址是不是相等。即，判断两个对象是不是同一个对象。(基本数据类型 == 比较的是值，引用数据类型 == 比较的是内存地址)
equals()
它的作用也是判断两个对象是否相等。但它一般有两种使用情况：
情况1：类没有覆盖 equals() 方法。则通过 equals() 比较该类的两个对象时，等价于通过“==”比较这两个对象。
情况2：类覆盖了 equals() 方法。一般，我们都覆盖 equals() 方法来两个对象的内容相等；若它们的内容相等，则返回 true (即，认为这两个对象相等)。
String中的equals方法
String中的equals方法是被重写过的，因为object的equals方法是比较的对象的内存地址，而String的equals方法比较的是对象的值。
当创建String类型的对象时，虚拟机会在常量池中查找有没有已经存在的值和要创建的值相同的对象，如果有就把它赋给当前引用。如果没有就在常量池中重新创建一个String对象。
为什么重写equals要重写hashcode
1.使用hashcode方法提前校验，可以避免每一次比对都调用equals方法，提高效率
2.保证是同一个对象，如果重写了equals方法，而没有重写hashcode方法，会出现equals相等的对象，hashcode不相等的情况，重写hashcode方法就是为了避免这种情况的出现。
B树 vs B+树
B树
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
结构
排序方式：
所有节点关键字是按递增次序排列，并遵循左小右大原则；
子节点数
非叶节点的子节点数>1，且<=M ，且M>=2，空树除外
M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉
关键字数
枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null
查找
获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点
拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点
拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；
插入
- （1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
- （2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;
- （2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;
>阶数-1就需要拆分成两个
删除
- （1）节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
- （2）满足节点本身比左边节点大，比右边节点小的排序规则;
- （3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
- （2）满足节点本身比左边节点大，比右边节点小的排序规则;
- （3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
<阶数/2 需要合并 先子后父
B+树
内结点不存放数据, 只存放数据索引+页号, 一个内结点页存放更多索引信息, 更快的缩小范围
只有叶子结点存放数据, 可以存放完整的数据或者数据的指针
叶子结点从小到大排列, 每层的页之间以双向链表的形式互相连接
- B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B*树
B*树是B+树的变种
B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3*m)）
B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），
如果兄弟节点未满则向兄弟节点转移关键字，
如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；
如果兄弟节点未满则向兄弟节点转移关键字，
如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；
B树总结
1、相同思想和策略
从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；
2、不同的方式的磁盘空间利用
不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；
从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；
2、不同的方式的磁盘空间利用
不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；
StringBuffer vs StringBuilder
- StringBuffer 线程安全, 方法+synchronized
StringBuilder底层是什么类型, 如何扩容
- 继承AbstractStringBuilder , 底层实现是char[] 数组
- 初始默认容量是16 super(16)
- 扩容, super.append(obj)
- 计算当前使用的容量+新的append的对象的长度 是否>char[] 数组的长度, 需要时扩容到这个长度
StringBuilder底层是什么类型, 如何扩容
- 继承AbstractStringBuilder , 底层实现是char[] 数组
- 初始默认容量是16 super(16)
- 扩容, super.append(obj)
- 计算当前使用的容量+新的append的对象的长度 是否>char[] 数组的长度, 需要时扩容到这个长度
fast-fail
什么是fast-fail
它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制
假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
fail-fast产生原因
程序在对 collection 进行迭代时，某个线程对该 collection 在结构上对其做了修改，这时迭代器就会抛出 ConcurrentModificationException 异常信息，从而产生 fail-fast。
ArrayList中无论add、remove、clear方法只要是涉及了改变ArrayList元素的个数的方法都会导致modCount的改变。
所以我们这里可以初步判断由于expectedModCount 得值与modCount的改变不同步，导致两者之间不等从而产生fail-fast机制
所以我们这里可以初步判断由于expectedModCount 得值与modCount的改变不同步，导致两者之间不等从而产生fail-fast机制
有两个线程（线程A，线程B），其中线程A负责遍历list、线程B修改list。
线程A在遍历list过程的某个时候（此时expectedModCount = modCount=N），线程启动，
同时线程B增加一个元素，这是modCount的值发生改变（modCount + 1 = N + 1）。
线程A继续遍历执行next方法时，通告checkForComodification方法发现expectedModCount = N ，而modCount = N + 1，两者不等，
这时就抛出ConcurrentModificationException 异常，从而产生fail-fast机制。
线程A在遍历list过程的某个时候（此时expectedModCount = modCount=N），线程启动，
同时线程B增加一个元素，这是modCount的值发生改变（modCount + 1 = N + 1）。
线程A继续遍历执行next方法时，通告checkForComodification方法发现expectedModCount = N ，而modCount = N + 1，两者不等，
这时就抛出ConcurrentModificationException 异常，从而产生fail-fast机制。
fail-fast解决办法
在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList，这样就可以解决。但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。
使用CopyOnWriteArrayList来替换ArrayList
CopyOnWriteArrayList
所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的
适用场景
1：在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。
2：当遍历操作的数量大大超过可变操作的数量时
copy原来的array，再在copy数组上进行add操作，这样做就完全不会影响COWIterator中的array了。
- 任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，
- 这样就不会影响COWIterator中的数据了，修改完成之后改变原有数据的引用即可。
- 同时这样造成的代价就是产生大量的对象，同时数组的copy也是相当有损耗的。
- 这样就不会影响COWIterator中的数据了，修改完成之后改变原有数据的引用即可。
- 同时这样造成的代价就是产生大量的对象，同时数组的copy也是相当有损耗的。
深拷贝 vs 浅拷贝
浅拷贝
被复制对象的所有变量都含有与原来的对象相同的值，而所有的对其他对象的引用仍然指向原来的对象。
即对象的浅拷贝会对“主”对象进行拷贝，但不会复制主对象里面的对象。”里面的对象“会在原来的对象和它的副本之间共享。
即对象的浅拷贝会对“主”对象进行拷贝，但不会复制主对象里面的对象。”里面的对象“会在原来的对象和它的副本之间共享。
深拷贝
深拷贝是一个整个独立的对象拷贝，深拷贝会拷贝所有的属性,并拷贝属性指向的动态分配的内存。当对象和它所引用的对象一起拷贝时即发生深拷贝。深拷贝相比于浅拷贝速度较慢并且花销较大。
深拷贝把要复制的对象所引用的对象都复制了一遍。
0 条评论
下一页
