散列表即哈希表是一种相当重要的数据结构, 其应用场景极为丰富, 好多缓存技术诸如的关键实际上就是于内存里维护一张规模较大的哈希表, 并且其实现原理常常在各类面试题里出现, 重要程度显而易见。本文会针对java集合框架中相应实现的实现原理予以讲解, 随后会对JDK7的源码展开分析。一、什么是哈希表在展开对于哈希表的讨论以前, 我们要去先大概知晓一下其他的数据结构, 在进行新增这个动作, 查找那个做法等基础操作时, 所执行的性能情况。一段接着一段连续的存储单元, 被用来存储数据从而形成数组。给定下标的查找, 其时间复杂度是O(1) , 通过给定值查找时, 要对数组进行遍历, 逐个比对给定关键字和数组元素, 这时候时间复杂度是O(n) , 当然, 针对有序数组而言, 能采用二分查找, 插值查找, 斐波那契查找这类方式, 把查找复杂度提升为O(logn) , 对于一般的插入删除操作, 由于涉及数组元素的移动, 平均复杂度是O(n)。线性链表, 在找到指定操作位置之后, 对于链表的新增、删除等操作, 仅仅只需要对结点间的引用予以处理就行, 其时间复杂度是O(1), 然而查找操作要遍历链表逐个进行比对, 复杂度为O(n)。有一棵二叉树, 它是相对平衡的有序二叉树, 针对这棵二叉树, 进行插入操作, 进行查找操作, 进行删除等操作, 每个操作的平均复杂度都为O(logn)。哈希表, 相比那几种数据结构而言, 在其中开展添加操作, 开展删除操作, 开展查找等操作, 其性能是十分高的, 在不把哈希冲突考虑进去的情形下, 仅仅需要一次定位便能够完成, 时间复杂度为O(1), 接下来我们就要去瞧瞧哈希表是怎样达成取得惊艳的常数阶O(1)的。我们清楚, 数据结构的物理存储结构仅有两种, 即顺序存储结构与链式存储结构, 像栈、队列、树、图等是基于逻辑结构进行抽象的, 映射至内存中, 同样是这两种物理组织形式, 然而在上面我们提及过, 在数组里依据下标查找某个元素, 一次定位便可达成, 哈希表运用了这种特性, 哈希表的主干是数组。例如, 我们要是想要新增或者查找某一个元素, 我们借助把当前元素的关键字经由某个函数映射到数组里的某一个位置, 凭借数组下标一次定位就能够完成操作。存储位置 f(关键字)其中, 被称作哈希函数的通常便是这个函数f, 该函数设计的好坏状况会对哈希表的优劣产生直接影响。比如说, 在哈希表里进行插入操作这种情况下:执行查找操作时, 道理是一样的, 要先透过哈希函数算出实际用于存储的地址, 接着从数组里对应的那个地址把所需内容取出来才行。哈希冲突然而世间之事不存在绝对的完美, 要是存在两个不一样的元素, 经由哈希函数所获取的实际存储地址是一样的该如何处理呢? 也就是说, 当针对某个元素开展哈希运算, 获取到一个存储地址, 而后准备进行插入操作时, 却发觉此地址已被其他元素给占用了, 实际上这便是所谓的哈希冲突, 也称作哈希碰撞。接下来要说的, 是先前我们已经提到过的, 哈希函数设计占据重要地位, 优良的的哈希器能够尽最大可能确保计算操作简易且散列地址分配均匀, 然而, 我们必须明确知晓的是, 数组是一块具备连续性的固定尺寸的内存区域, 哪怕是再优质的哈希手段也没办法确保所获取的存储地址绝对不会产生冲突。那么, 哈希冲突该通过怎样的方式予以解决呢? 哈希冲突的解决办法存在多种形式: 开放定址法即出现哈希冲突时继续寻觅下一块未被占用式的存储地址, 再散列函数法, 链地址法, 就算是选用了链地址法也就是数组与链表相结合的那种方式。二、实现原理Entry数组是主干, 存在着, Entry是基本组成单元, 一个Entry包含一个key-value键值对, 每一个都是如此。//HashMap的主干数组可以看到就是一个Entry数组初始值为空数组{}主干数组的长度一定是2的次幂至于为什么这么做后面会有详细分析。transientEntry[] table (Entry[]) EMPTY_TABLE;Entry是中的一个静态内部类。代码如下staticclassEntryimplementsMap.Entry{finalK key; V value; Entrynext;//存储指向下一个Entry的引用单链表结构inthash;//对key的hashcode值进行hash运算后得到的值存储在Entry避免重复计算/*** Creates new entry.*/Entry(inth, K k, V v, Entryn) { valuev; nextn; keyk; hashh; }所以的整体结构如下简要来讲, 是由数组与链表共同构成的, 其中数组作为主体部分, 链表主要是为解决哈希冲突而存在的, 要是定位到的数组位置不含有链表也就是当前entry的next指向null, 那么对于查找以及添加等操作而言速度都是很快的, 仅仅需要一次寻址便可要是定位到的数组含有链表, 对于添加操作, 其时间复杂度是O(n), 首先要遍历链表, 存在的话就进行覆盖, 不然的话就新增对于查找操作来说, 依旧需要遍历链表, 接着通过key对象的方法逐个进行比对查找。所以性能考虑中的链表出现越少性能才会越好。其他几个重要字段//实际存储的key-value键值对的个数transientintsize;//阈值当table {}时该值为初始容量初始容量默认为16当table被填充了也就是为table分配内存空间后threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold后面会详细谈到intthreshold;//负载因子代表了table的填充度有多少默认是0.75finalfloatloadFactor;//用于快速失败由于HashMap非线程安全在对HashMap进行迭代时如果期间其他线程的参与导致HashMap的结构发生变化了比如putremove等操作需要抛出异常ConcurrentModificationExceptiontransientintmodCount;存在4个构造器, 对于其他构造器而言, 要是用户并未传入和那两个参数, 便会采用默认值。默认为16默认为0.75我们看下其中一个publicHashMap(intinitialCapacity,floatloadFactor) {//此处对传入的初始容量进行校验最大不能超过MAXIMUM_CAPACITY 130(230)if(initialCapacity 0)thrownewIllegalArgumentException(Illegal initial capacity: initialCapacity);if(initialCapacity MAXIMUM_CAPACITY) initialCapacityMAXIMUM_CAPACITY;if(loadFactor 0 ||Float.isNaN(loadFactor))thrownewIllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor; thresholdinitialCapacity; init();//init方法在HashMap中没有实际实现不过在其子类如 linkedHashMap中就会有对应实现}据上面这段代码所示, 于常规构造器里, 未给数组table分配内存空间, 不过存在一个入参为指定Map的构造器属于例外情况, 它是在执行put操作之际才切实构建table数组的。OK,接下来我们来看看put操作的实现吧publicV put(K key, V value) {//如果table数组为空数组{}进行数组填充为table分配实际内存空间入参为threshold此时threshold为initialCapacity 默认是14(2416)if(table EMPTY_TABLE) { inflateTable(threshold); }//如果key为null存储位置为table[0]或table[0]的冲突链上if(key null)returnputForNullKey(value);inthash hash(key);//对key的hashcode进一步计算确保散列均匀inti indexFor(hash, table.length);//获取在table中的实际位置for(Entry e table[i]; e !null; e e.next) {//如果该对应数据已存在执行覆盖操作。用新value替换旧value并返回旧valueObject k;if(e.hash hash ((k e.key) key ||key.equals(k))) { V oldValuee.value; e.valuevalue; e.recordAccess(this);returnoldValue; } } modCount;//保证并发访问时若HashMap内部结构发生变化快速响应失败addEntry(hash, key, value, i);//新增一个entryreturnnull; }先来看看这个方法privatevoidinflateTable(inttoSize) {intcapacity roundUpToPowerOf2(toSize);//capacity一定是2的次幂threshold (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1);//此处为threshold赋值取capacity*loadFactor和MAXIMUM_CAPACITY1的最小值capaticy一定不会超过MAXIMUM_CAPACITY除非loadFactor大于1tablenewEntry[capacity]; initHashSeedAsNeeded(capacity); }这种办法是用于给主干数组table于内存里去分配存储空间的, 借助()能够保证对于大于或者等于的那个最接近之二次幂, 举例来说, 要是13, 那么16要是16, 16要是17, 32。privatestaticintroundUpToPowerOf2(intnumber) {//assert number 0 : number must be non-negative;returnnumber MAXIMUM_CAPACITY?MAXIMUM_CAPACITY : (number 1) ? Integer.highestOneBit((number - 1) 1) : 1; }在此之中的这段处理, 致使数组长度必然为2的次幂, 其中的.是用以获取最左边的bit其他bit位皆为0所表示的数值。hash函数//这是一个神奇的函数用了很多的异或移位等运算对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀finalinthash(Object k) {inth hashSeed;if(0 ! h kinstanceofString) {returnsun.misc.Hashing.stringHash32((String) k); } h^k.hashCode(); h^ (h 20) ^ (h 12);returnh ^ (h 7) ^ (h 4); }将以上经hash函数算得的值, 借助进一步处理, 从而去获取实际的存储位置。/*** 返回数组下标*/staticintindexFor(inth,intlength) {returnh (length-1); }h与-1确保所获取的index必然处于数组范围之内, 比如说, 默认容量是16, -1等于15, h等于18, 将其转换成二进制来进行计算用标点符号隔开, 计算为标点符号隔开1 0 0 1 0 0 1 1 1 1 __________________ 0 0 0 1 0 2经过最终的计算得出, index 的值为 2。存在一些版本, 针对此处的计算会采用取模运算, 如此也能够确保 index 必定处于数组范围之内, 然而对于计算机而言, 位运算的性能会更高一些, 中存在很多位运算所以最终存储位置的确定流程是这样的再来看看的实现voidaddEntry(inthash, K key, V value,intbucketIndex) {if((size threshold) (null!table[bucketIndex])) { resize(2 *table.length);//当size超过临界阈值threshold并且即将发生哈希冲突时进行扩容hash (null! key) ? hash(key) : 0; bucketIndexindexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }由上述代码能够知悉, 在出现哈希冲突且size大于阈值之际, 需开展数组扩容, 扩容之时, 要创建一个长度为先前数组两倍的全新数组, 接着把当下的Entry数组里的元素全都传输过去, 扩容后的新数组长度是之前的两倍, 故而扩容相对而言是消耗资源的行为。三、为何的数组长度一定是2的次幂我们来继续看上面提到的方法voidresize(intnewCapacity) { Entry[] oldTabletable;intoldCapacity oldTable.length;if(oldCapacity MAXIMUM_CAPACITY) { thresholdInteger.MAX_VALUE;return; } Entry[] newTablenewEntry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); tablenewTable; threshold (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1); }一旦数组实施扩容, 其长度产生改变, 鉴于存储位置是index等于h与负1进行按位与运算所得的值所以index也存在发生变化的可能性此情势下就得重新去计算index, 那我们先着手瞧瞧这个方法。voidtransfer(Entry[] newTable,booleanrehash) {intnewCapacity newTable.length;//for循环中的代码逐个遍历链表重新计算索引位置将老数组数据复制到新数组中去数组不存储实际数据所以仅仅是拷贝引用而已for(Entrye : table) {while(null!e) { Entrynext e.next;if(rehash) { e.hashnull e.key ? 0: hash(e.key); }inti indexFor(e.hash, newCapacity);//将当前entry的next链指向新的索引位置,newTable[i]有可能为空有可能也是个entry链如果是entry链直接在链表头部插入。e.nextnewTable[i]; newTable[i]e; enext; } } }采用这个方法, 会对老数组里的数据, 逐项依照链表的方式去遍历, 而后抛入新的经历扩容之后的数组当中。我们计算数组索引位置的方式是, 先针对key值开展hash扰乱运算, 接着借助和 -1做位运算, 以此得出最终的数组索引位置。数组的长度必然始终维持为2的次幂形式, 举例来说, 假设16, 其对应的二进制呈现为10000 , 那么-1所对应的数值便是15 , 而其二进制呈现为01111 , 同样的道理, 当扩容之后数组的长度变为32 , 其对应的二进制呈现为 , -1所对应的数值为31 , 其二进制呈现为。图中所示, 我们能看到这般能确保低位皆为1, 扩容以后仅有一位存在差异, 也就是最左位的1多了出来, 如此一来, 于通过h(-1)之际, 只要h所对应的最左边那个差异位是0, 便能够保障所获新数组索引与老数组索引相同(极大减少了先前已散列优良的老数组的数据位置再度调换), 此乃个人见解。另外, 数组的长度维持在2的次幂, -1的较低位置全部是1, 这会致使所获取的数组索引index更为均匀, 举例来说:我们能够看到, 上面所进行的运算, 高位是不会对最终结果造成后果的, hash函数运用各种位运算或许也是为了让低位更加具有散列性, 我们仅仅着重于低位bit。要是低位全都处于1的状态, 那么对于h的低位部分来讲, 任何一位的改变都会对阵最终做出影响。也就是说, 要获取到index21的这个存储位置, h的低位仅仅存在这一种组合方式。这同样为数组长度被设计成必须是2的次幂的缘由。若并非2的次幂, 即低位并非全为1, 在此情形时, 想要让index等于21, h的低位部分便不再具备唯一性, 哈希冲突的几率会变得更大, 与此同时, index所对应的这个bit位不管怎样都不会等于1, 而与之对应的那些数组位置就被白白地浪费掉了。get方法publicV get(Object key) {//如果key为null,则直接去table[0]处去检索即可。if(key null)returngetForNullKey(); Entryentry getEntry(key);returnnull entry ?null: entry.getValue(); }get方法凭借key值来返回相应value, 要是key为null, 便直接前往table。处检索。我们再看一下这个方法finalEntrygetEntry(Object key) {if(size 0) {returnnull; }//通过key的hashcode值计算hash值inthash (key null) ? 0: hash(key);//indexFor (hashlength-1) 获取最终数组索引然后遍历链表通过equals方法比对找出对应记录for(Entry e table[indexFor(hash, table.length)]; e!null; ee.next) { Object k;if(e.hash hash ((k e.key) key || (key !nullkey.equals(k))))returne; }returnnull; }能够看得出, get方式的达成相较简易, key()经由hash抵达最终索引地方, 寻觅到对应地点table。还需去查看一下是不是存在链表, 把链表进行遍历操作, 借助key办法去比对查找相应的记录。需要留意的是, 有人认为在通过上面的方式定位到数组位置之后进而遍历链表时, e.hash hash这个判断不具备必要性, 仅仅凭借判断就行。其实并非如此, 试着去想一下, 假如传入的那个key对象, 对方法进行了重写, 然而却存在没有重写的情况, 并且恰好这个对象定位到了这个数组所处位置, 要是仅仅运用判断, 或许会认为是相等的, 可是它和当前对象并不一致, 面对这种情形, 依据相应的约定, 不可以返回当前对象, 而是应当返回null, 之后的例子将会作出进一步的解释。四、重写方法需同时重写方法针对源码的分析介绍就讲到这儿了, 最后我们再来谈论一下常常被提及的一个问题, 各种资料里都会有所提及, “重写之际也要一并覆盖”, 我们列举一个小例子来看一看, 要是重写了却不进行重写会出现怎样的问题。/*** Created by chengxiao on 2016/11/15.*/publicclassMyTest {privatestaticclassPerson{intidCard; String name;publicPerson(intidCard, String name) {this.idCard idCard;this.name name; } Overridepublicbooleanequals(Object o) {if(thiso) {returntrue; }if(o null|| getClass() !o.getClass()){returnfalse; } Person person(Person) o;//两个对象是否等值通过idCard来确定returnthis.idCard person.idCard; } }publicstaticvoidmain(String []args){ HashMapmap newHashMap(); Person personnewPerson(1234,乔峰);//put到hashmap中去map.put(person,天龙八部);//get取出从逻辑上讲应该能输出“天龙八部”System.out.println(结果:map.get(newPerson(1234,萧峰))); } }实际输出结果结果null如果我们已经对的原理有了一定了解这个结果就不难理解了。当中我们在开展get以及put操作之际, 所运用的key在逻辑层面是等值的借助比较是相等的, 然而鉴于没有重写方法, 所以在put操作时, key()经过hash之后到达最终索引位置 , 而凭借key去取出value的时候也是key()经过hash之后到达最终索引位置, 由于二者不相等, 致使没能定位到一个数组位置进而返回逻辑上错误的值null也存在碰巧定位到一个数组位置的情况, 不过依旧会判断其entry的hash值是否相等, 上面get方法里有提及。所以, 在对方法进行重新编写之际, 务必要留意重新编写的方法, 与此同时还得担保经由判定相等的两个对象, 调用该方法时要返回相同的整数值。然而要是判定不相等的两个对象, 它们可为相同只不过会出现哈希冲突现象, 应当尽可能予以规避。五、总结此文讲述了实现的原理, 还结合源码予以了更深层次的剖析, 其中也涵盖了一些源码细节的设计缘由, 末尾简要说明了重写之际为何要有重写方法。期望这篇文章能够对诸位有所助益, 同时也欢迎探讨指正, 多谢支持