大家好,又见面了,我是你们的朋友全栈君。
顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log N),搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。 当向该结构中: 插入元素 根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功 该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(HashTable)(或者称散列表)
不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
*由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一 个问题,冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率。*而不能完全避免哈希冲突。
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:
哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单
用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快
负载因子 = 0.75;
所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。(2倍扩容)
HashMap的扩容时取决于threshold, 而threshold取决于loadFactor, loadFactor(负载因子)HashMap的默认值是0.75(3/4), 那么为什么当HashMap的容量超过3/4时就需要扩容了呢? 为什么不是1/2扩容 或者 等于table.length时扩容呢?
根据统计学的结果, hash冲突是符合泊松分布的, 而冲突概率最小的是在7-8之间, 都小于百万分之一了; 所以HashMap.loadFactor选取只要在7-8之间的任意值即可, 但是为什么就选了3/4这个值? HashMap.loadFactor的选值是3/4就能理解了, table.length * 3/4可以被优化为(table.length >> 2) << 2) – (table.length >> 2) == table.length – (table.lenght >> 2), JAVA的位运算比乘除的效率更高, 所以取3/4在保证hash冲突小的情况下兼顾了效率;
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/150594.html原文链接:https://javaforall.cn