HashMap和HashTable
1、继承不同
HashMap继承了AbstractMap，AbstractMap实现了Map接口
HashTable继承了Dictionary类
2、线程安全不同
HashMap不是线程安全的，HashTable是线程安全的
3、允许null值
HashMap允许key和value为空，而HashTable不允许
4、遍历方式实现不同
HashMap的迭代器是fail-fast迭代器，HashTable的enumerator迭代器不是fail-fast的
5、哈希值的使用不同
HashMap重新计算哈希值，HashTable直接使用对象的哈希值
6、初始容量和扩容方式不同
HashMap初始大小为16，扩容大小一定是2的指数
HashTable初始大小为11，扩容大小为old*2+1
7、hashmap新增红黑树结构
当碰撞链表过长时，就把链表转为红黑树
哈希表
构造方法
1、直接定址法
取关键字或关键字的某个线性函数值为散列地址
特点：关键字连续时较方便，但关键字不连续时将造成内存单元的大量浪费
2、数字分析法
取关键字中取值比较均匀的若干数位作为哈希值。
特点：适用于关键字全部已知，并要对关键字中每一位进行分析
3、平方取中法
取关键字平方后中间几位作为哈希地址
特点：因为平均值的中间部分跟关键字的每一位都有关，出现随机值的概率较大
4、分段叠加法
按哈希表地址位数将哈希表分为位数相等的几段（最后一段可以较短），然后将这几部分相加，舍弃最高位的进位得到哈希值。
具体分为：移位法与折叠法
移位法：将每部分低位对其相加
折叠法：从一段向另一端沿分割线来回折叠（奇数段为正序，偶数段为倒序）
例如关键字123603247112020,哈希表长度为1000，则应把关键字分成3位一段
image
移位法得到105，折叠法得到907
5、伪随机数法
采用伪随机函数作为哈希函数
6、除留余数法
用关键字除以某个不大于哈希表长度的数，取余数作为哈希值。
冲突处理方法
1、开放定址法
当关键字key的哈希值p=H（key）出现冲突时，以p为基础产生新的哈希值p1，如果p1仍冲突，则产生p2，以此类推。
函数形式如下：
Hi = (H(key) + di) % m
根据di的不同分为
（1）线性探测
di = 1， 2， 3， …… ，（m-1）
（2）平方探测
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
（3）伪随机探测
di = 伪随机数序列
2、再哈希法
构造多个不同的哈希函数，当出现冲突时，使用新的哈希函数
3、链地址法
将散列到同一位置的冲突元素存入一个链表中
4、建立一个公共溢出区
将哈希表分为基本表和溢出表
左旋和右旋
左旋：
image
右旋
image
红黑树
红黑树是一颗特殊的二叉查找树，除了二叉查找树的所有性质
1、若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2、若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
3、任意节点的左右子树也为二叉查找树
4、没有键值相等的节点
还满足
1、每个节点要么是红的要么是黑的
2、根节点是黑的
3、每个叶节点（null节点）是黑的
4、如果一个节点是红的，那么它的两个儿子都是黑的
5、任意节点到叶节点（null节点）的每条路径都包含相同数目的黑节点
红黑树保证没有一条路径比另一条路径长出两倍，保证了自身是接近平衡的二叉树，能保证在最坏的情况下查找的时间复杂度为O（logN），而二叉查找树最坏为O（N）
image
红黑树相比BST和AVL树有什么优点
红黑树牺牲了严格的高度平衡为代价，只要求部分达到部分平衡条件，降低了对旋转的要求，从而提高了性能。红黑树能够以O（logN）的时间复杂度进行添加，删除，查找。由于它的设计，任何不平衡都可以在三次旋转之内解决。
1、相比BST（二叉搜索树）
红黑树的最长路径不大于最短路径两倍，保证了最差搜索效率为O（logN）,而二叉搜索树最差效率会达到O（N）
2、相比AVL（平衡二叉树）
（1）红黑树的查询性能略逊于平衡二叉树，因为它比平衡二叉树会最多多一层。
（2）红黑树在插入删除上要优于平衡二叉树，红黑树使用非严格的高度平衡换取增删节点时旋转次数的减少，任何不平衡都会在三次旋转之内解决，但是平衡二叉树旋转次数有时会比红黑树要多。所以红黑树的插入删除效率更高。
网友评论