一个域名可以建几个网站,公司公司手机网站制作,不是网站开发语言的是,网站表格怎么做前言
在弄清楚HashMap之前先介绍一下使用到的数据结构#xff0c;在jdk1.8之后HashMap中为了优化效率加入了红黑树这种数据结构。
树
在计算机科学中#xff0c;树#xff08;英语#xff1a;tree#xff09;是一种抽象数据类型#xff08;ADT#xff09;或是实作这种…前言
在弄清楚HashMap之前先介绍一下使用到的数据结构在jdk1.8之后HashMap中为了优化效率加入了红黑树这种数据结构。
树
在计算机科学中树英语tree是一种抽象数据类型ADT或是实作这种抽象数据类型的数据结构用来模拟具有树状结构性质的数据集合。它是由nn0个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。它具有以下的特点
每个节点都只有有限个子节点或无子节点没有父节点的节点称为根节点每一个非根节点有且只有一个父节点除了根节点外每个子节点可以分为多个不相交的子树树里面没有环路(cycle) 在分类上包含了二叉树、二叉查找树、红黑树、B树、B树等。 1、二叉树
每个节点最多含有两个子节点分别为左子节点和右子节点。不要求每个节点都有两个子节点有的只有左有的只有右子节点二叉树每个节点的左子树和右子树也分别满足前两条定义
2、二叉搜索树
在树种的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值不会出现键值相等的节点通常情况下二叉树搜索的时间复杂度为O(log n) 因为他不会自旋所以会出现一种最坏的情况左右子树极度不平衡
3、红黑树
节点要么是红色要么是黑色跟节点是黑色叶子节点都是黑色的空节点红黑树的红色节点的子节点都是黑色从任意节点到叶子节点的所以路径都包含相同数目的黑色节点在进行添加或者删除后如果不满足上面的五条定义则会发生旋转调整操作查找、删除、添加的操作时间复杂度都是O(log n)
散列表
散列表又名hash表是根据键(key)直接访问在内存存储位置值(value)的数据结构它是由数组演化而来的利用了数组支持按照下标进行随机访问数据的特性 将键(key)映射为数组下标的函数叫做散列函数。可以表示为hashValue hash(key) 散列函数的基本要求
散列函数计算得到的散列值必须是大于等于0的正整数因为hashValue需要作为数组的下标。如果key1 key2那么经过hash后得到的哈希值也必相同即hash(key1) hash(key2)如果key1 ! key2那么经过hash后得到的哈希值也必相同即hash(key1) ! hash(key2)
散列冲突
实际的情况下想找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的。从而就会造成一种现象就是多个key通过hash运算转换之后映射到同一个数组下标位置这种情况被称之为散列冲突(或者哈希冲突、哈希碰撞)
拉链法
为了解决散列冲突一般都会采用一种叫拉链法的方式解决。 在散列表中数组的每个下标位置我们可以称之为桶每个桶会对应一条链表所有散列值相同的元素我们都放到相同槽位对应的链表中这种方式就叫拉链法
插入操作通过散列函数计算出对应的散列槽位将其插入到对应链表中即可插入的时间复杂度是O(1)当查找、删除一个元素时我们同样通过散列函数计算出对应的槽然后遍历链表查找或者删除 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)散列表可能会退化为链表查询的时间复杂度就从O(1)退化为O(n)将链表法中的链表改造为其他高效的动态数据结构比如红黑树查询的时间复杂度是O(log n) 而且使用红黑树可以有效的防止DDos 攻击 一、简介
HashMap是Map中的重要实现类它是一个散列表存储的内容是键值对keyvalue映射。HashMap是非线程安全的。HashMap中允许存储null的键和值键是唯一的。
在JDK1.8以前HashMap的底层数据结构是纯粹的数组链表结构。由于数组具有读取快增删慢的特点而链表具有读取慢增删快的特点HashMap将二者相结合并且没有使用同步锁进行修饰它的性能较好。数组是HashMap的主体链表则是为了解决哈希冲突而引入。此处解决哈希冲突的具体方法为拉链法
二、源码解析
1、put方法
1.1、常见属性
扩容阈值 数组容量 * 加载因子 //默认的初始容量static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16 //默认的加载因子 static final float DEFAULT_LOAD_FACTOR 0.75f;//存储数据的数组transient NodeK,V[] table;//容量transient int size;
1.2、构造函数 //默认无参构造public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // 指定加载因子为默认加载因子 0.75}HashMap是懒惰创建数组的在创建对象的时候并没有初始化数组在无参的构造函数中设置了默认的加载因子
1.3、put方法
流程图 具体源码 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/** * 计算hash值的方法*/static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}/** * 具体执行put添加方法*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//判断数组是否初始化(数组初始化是在第一次put的时候)if ((tab table) null || (n tab.length) 0)//如果未初始化调用resize()进行初始化n (tab resize()).length;//通过 运算符计算求出该数据(key)的数组下标并且判断该下标位置是否有数据if ((p tab[i (n - 1) hash]) null)//如果没有直接将数据放在该下标位置tab[i] newNode(hash, key, value, null);else { //该下标位置有数据的情况NodeK,V e; K k;//判断该下标位置的数据是否和当前新put的数据一样if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))//如果一样则直接覆盖valuee p;//判断是不是红黑树else if (p instanceof TreeNode) //如果是红黑树的话进行红黑树的具体添加操作e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);//如果都不是代表是链表else { //遍历链表for (int binCount 0; ; binCount) {//判断next节点是否为null是null代表遍历到链表尾部了if ((e p.next) null) {//把新值插入到尾部p.next newNode(hash, key, value, null);//插入数据后判断链表长度有大于等于8了没if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是则进行红黑树转换treeifyBin(tab, hash);break; //退出}//如果在链表中找到相同数据的值则进行修改操作if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;//把下一个节点赋值为当前节点p e;}}//判断e是否为null(e值为前面修改操作存放原数据的变量)if (e ! null) { // existing mapping for key//不为null的话证明是修改操作取出老值V oldValue e.value;if (!onlyIfAbsent || oldValue null)//把新值赋值给当前节点e.value value;afterNodeAccess(e);//返回老值return oldValue;}}//计算当前节点的修改次数modCount;//判断当前数组中的数据量是否大于扩容阈值if (size threshold)//进行扩容resize();afterNodeInsertion(evict);return null;}具体流程
判断键值对数组table是否为ull复杂执行resize()进行扩容(初始化)根据键值对key计算hash值得到数组索引判断table[i]hash值得到数组索引如果taale[i] null 条件成立直接新建节点添加 i. 判断table[i]的首个元素是否和key一样如果相同直接覆盖value ii. 判断table[i]是否为treeNode即table[i]是否为红黑树如果红黑树则直接在数中插入键值对 iii. 遍历table[i]链表的尾部插入数据然后判断链表长度是否大于8大于的话把链表转换为红黑树操作遍历过程中若发现key已经存在执行覆盖value
1.4 resize方法(扩容)
流程图 具体源码 final NodeK,V[] resize() {NodeK,V[] oldTab table;//如果当前数组为null的时候把oldCap 老数组容量设置为0int oldCap (oldTab null) ? 0 : oldTab.length;//老的扩容阈值int oldThr threshold;int newCap, newThr 0;//判断数组容量是否大于0大于0说明数组已经初始化if (oldCap 0) {//判断当前数组长度是否大于最大数组长度if (oldCap MAXIMUM_CAPACITY) {//如果是将扩容阈值直接设置为int类型的最大数值并且直接返回threshold Integer.MAX_VALUE;return oldTab;}//如果在最大长度访问内则需要扩容oldCap 1 oldCap * 2//并且判断是否大于16,else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold 等价于 oldCap * 2}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;//数组初始化的情况将阈值和扩容因子设置为默认值else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的时候扩容阈值没用阈值的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})//根据上边计算得出的容量 创建新的数组NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;//扩容操作判断不为null证明不是初始化数组if (oldTab ! null) {// 遍历数组for (int j 0; j oldCap; j) {NodeK,V e;//判断当前下标为j的数组如果不为null的话赋值给eif ((e oldTab[j]) ! null) {//将数组的位置设置为nulloldTab[j] null;//判断是否有下一个节点if (e.next null)//如果没有就查询计算在新数组中的下标并放进去newTab[e.hash (newCap - 1)] e;//有下个节点的情况并且判断是否已经树化else if (e instanceof TreeNode)//进行红黑树的操作((TreeNodeK,V)e).split(this, newTab, j, oldCap);//有下个节点的情况并且判还没有树化 else { // preserve orderNodeK,V loHead null, loTail null; //低位数组NodeK,V hiHead null, hiTail null; //高位数组NodeK,V next;遍历循环do {//取出next节点next e.next;//通过 操作计算出结果为0if ((e.hash oldCap) 0) {//如果低位为null则把e值放入低位2头if (loTail null)loHead e;//低位尾不是nullelse//将数据放入next节点loTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.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;}执行原理
在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次每次扩容都是达到了扩容阈值(数组长度*0.75)每次扩容的时候都是扩容之前容量的2倍;扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中 i.没有hash冲突的节点则直接使用e.hash(newCap-1)计算新数组的索引位置 ii.如果是红黑树走红黑树的添加 iii.如果是链表则需要遍历链表可能需要拆分链表判断(e.hasholdCap)是否为0该元素的位詈要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上 扩容时候怎么重新确定元素在数组中的位置我们看到是由 if ((e.hash oldCap) 0) 确定的。 hash HEX(97) 0110 0001
n HEX(16) 0001 0000
--------------------------结果 0000 0000
# e.hash oldCap 0 计算得到位置还是扩容前位置hash HEX(17) 0001 0001 n HEX(16) 0001 0000
--------------------------结果 0001 0000
# e.hash oldCap ! 0 计算得到位置是扩容前位置扩容前容量 get方法
public V get(Object key) {// 定义一个Node结点NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {// 数组中元素相等的情况if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;// bucket中不止一个结点if ((e first.next) ! null) {//判断是否为TreeNode树结点if (first instanceof TreeNode)//通过树的方法获取结点return ((TreeNodeK,V)first).getTreeNode(hash, key);do {//通过链表遍历获取结点if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}// 找不到就返回nullreturn null;
}
常见问题
1、索引如何计算hashCode都有了为何还要使用hash()方法数组容量为何是2的n次幂 先计算key的hashCode()再进行调用Hash()方法使用异或的方式扰动运算进行二次哈希最后再通过(n - 1) hash 与运算得到索引。使用该方式相当于hash % n取模运算 二次hash()是为了综合二进制的高位数据让哈希分布更加均匀减少哈希碰撞的概率计算公式(h key.hashCode()) ^ (h 16) 计算索引是如果是2的n次幂可以使用位与运算代替取模效率更高而且再扩容时hash lodCap 0 的元素留在原来位置为1的则到到扩容后的新位置新位置旧位置lodCap 计算方式hash length 使用二次hash值和原始容量做运算如果结果是0则位置不变如果不是0则移动到新的位置新的位置计算方式原始数组容量原始下标新的位置 使用2的n次幂主要也是为了可以更好的配合优化效率使得下标分布得更加的均匀
2、HashMap的put方法流程1.7和1.8有何不同
HashMap是懒惰创建数组的首次使用才创建数组计算索引桶下标 首先得到key的hash值在经过一次hash()方法计算出二次hash的值**计算方式为(h key.hashCode()) ^ (h 16)**把hash值通过无符号右移然后再和原本的hash值进行异或计算这样的作用主要是为了打乱真正参与计算的低16位可以有效的做到扰乱运算的效果减少了哈希碰撞的概率然后再拿整个二次hash的值和数组的容量进行除留余数法取得的余数就是最终的桶下标计算方式为n-1hash 把数组长度-1再通过和hash值进行与运算。相当于使用hash值去和数组的长度n做取余% % 运算使用做运算主要也是为了可以有效的提高运算的效率1.7没有该优化 如果该桶下标还没人占用则创建Node节点返回如果该桶下标已经被占用则会去逐个的和各个节点进行比较看hash值和equals()是否都相对如果都相等代表是同一个key则进行覆盖修改如果不相同则添加 当已经TreeNode走红黑树的添加或更新逻辑如果是普通的Node走链表的添加或更新逻辑如果链表长度超过树化阈值8时走树化逻辑执行树化操作前提条件是数组长度达到64 返回前还会检查容量是否超过了扩容的阈值数组长度/加载因子一但超过则会进行扩容不同 链表插入时1.7使用的是头插法从链表头部插入1.8使用的是尾插法从链表尾部插入 1.7是大于等于阈值且没有空位才扩容如果有空位则不会扩容而是继续放在计算出来的桶下标的位置上而1.8是大于等于阈值就扩容1.8在扩容计算Node节点时会优化
