自己做的小说网站要交税吗,衡阳网站优化,wordpress主题汉化软件,手机制作gifhash是什么#xff1f;
hash也称为散列#xff0c;就是把任意长度的输入#xff0c;通过散列算法#xff0c;变成固定长度的输出#xff0c;这个输出值就是散列值。
举例来说明一下什么是hash#xff1a;
假设我们要把1~12存入到一个大小是5的hash表中#xff0c;我们…hash是什么
hash也称为散列就是把任意长度的输入通过散列算法变成固定长度的输出这个输出值就是散列值。
举例来说明一下什么是hash
假设我们要把1~12存入到一个大小是5的hash表中我们就是用indexnumber%5的公式去计算索引存入数据 hash是一个神奇的数据结构可以以接近O(1)的时间复杂度去进行查询
但是很快我们就会发现一个问题就是相同的余数的值储存在同一个索引下这样就会造成一个问题比如我查询8是否存储在结构中我们能直接访问array[3]这个位置里面存储8会返回给我们的一个true然后如果我们想要查询13是否存在该结构中还是会去array[3]中查找发现里面没存有数据13返回false
如何解决hash冲突
首先先来说一下哈希冲突哈希冲突Hash Collision是指在使用哈希表存储数据时两个或多个不同的键Key被哈希函数映射到同一个位置的情况。这种情况会导致数据的存储和查找变得复杂因此需要采取一些措施来解决哈希冲突。
解决hash冲突的方法
1.拉链法:
链地址法是一种处理哈希冲突的方法它是将所有散列到同一个地址的数据项存储在一个单链表中。这样当查找某个数据项时只需要在对应的链表中进行搜索即可。例如HashMap 在解决存储对象存在 hash 冲突的问题时采用的就是链地址法将相同 hash 值的对象以链表的形式进行存储。 2.再hash法
在发生冲突的时候再用另一个哈希函数算出哈希值直到算出的哈希值不同为止。
3.线性探测
就是发生hash冲突时往后面继续去找空的地方找到后把冲突的值放到空的散列值的里面。
hashmap源码 Ctrl鼠标左键点进去 先来看一下hash这个方法 定义了一个h如果keynull那么就返回0作为hash值如果不等于null那么首先把h无符号右移16位相当于保留了原哈希码的高16位并将它们放在低16位的位置同时丢弃了原始的低16位。然后这个右移后的值与原始的哈希码进行异或操作。异或操作的一个特性是任何数与0异或都保持不变而与自身异或则结果为0。这种变换有助于将哈希码的不同部分混合在一起从而增加哈希值的分布范围减少哈希冲突的可能性。这个称之为一次扰动每运算一次就算作一次扰动就是为了让hash码的每一位都参与运算并减少冲突。
hash这个函数就是给一个对象经过一个算法处理返回一串数字作为hash码。
然后我们回过来看putVal函数 首先是判断table是否为空如果是空的话先进行一个初始化
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)//如果数组中这个位置是空的那么直接创建一个新的点把keyhashvalue装进去tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) //先判断我们取得的hash值和p的这个hash值是不是一样如果一样再开始判定key是不是一样判断key相等的时候先判断两个key再判断两个key的值是不是一样如果一样就令epe p;else if (p instanceof TreeNode)//如果是树结点就把树结点按照树结点的方式传上去e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {//如果一开始的头不一样//循环遍历结点的链表//如果判断为空就在尾部插一个结点for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//一旦发现有相等的就直接跳出循环if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}//如果e不是空的那就直接把这个值赋给老的就是说当两次put操作的key相等的时候后面put的值会覆盖前面put的值if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;
}
1.如果hashmap是空的话也就是它内部的table数组是null在添加第一个元素的时候会进行初始化为table分配内存空间设置初始容量为16和加载因子0.75
2.对要插入的键计算hash值拿到hash值之后使用hash值得与table数组的长度来确定该键的存储位置万一出现了产生相同的hash值的情况下hashmap采用链表或红黑树链表大于8的时候用红黑树。如果该桶中没有元素就直接创建一个新的结点如果不是空就遍历链表或者红黑树查找是否存在相同的键存在相同的键就用新的键代替旧的键如果不存在就将新的结点添加到末尾红黑树就按红黑树规则插入
