微信网站建设报价单,重庆工业设计公司有哪些,阀门专业网站建设,招聘网站毕业设计文章目录 一、解决哈希冲突1.1闭散列1.1.1线性探测1.1.2二次探测 1.2开散列 二、模拟实现哈希表三、HashMap源码的一些相关内容 哈希#xff08;散列#xff09;方法#xff1a;构造一种存储结构#xff0c;通过某种函数使元素的存储位置与它的关键码之间能够建立 一 一 映… 文章目录 一、解决哈希冲突1.1闭散列1.1.1线性探测1.1.2二次探测 1.2开散列 二、模拟实现哈希表三、HashMap源码的一些相关内容 哈希散列方法构造一种存储结构通过某种函数使元素的存储位置与它的关键码之间能够建立 一 一 映射关系那么在查找时通过该函数就可以很快找到该元素。 哈希散列方法中的函数称为哈希散列函数构造出来的结构称为哈希表散列表。 例如在集合{12345}中哈希函数设置为hash(key)key%capacity。 哈希函数的选择和数据整体元素有关与单个元素没有直接关联。 对于哈希冲突避免冲突的方法有①设置合理的哈希函数 ②降低负载因子即提高散列表的长度负载因子填入表中的元素个数/散列表的长度解决冲突的方法有①闭散列 ②开散列 采用哈希处理一般所需空间都会比元素个数多否则产生冲突的概率就比较大所以哈希表相当于用空间来换取时间哈希表的时间复杂度是O1。搜索时二叉搜索树比哈希表效率低二叉搜索树的时间复杂度为O(logN)或O(N)哈希表的时间复杂度为O(1)。 hashCode()可以将对象转变为一个整数(为这个对象返回一个哈希值hashCode()被支持使用到哈希表当中)。 一、解决哈希冲突
1.1闭散列
闭散列法也叫开放定址法发生哈希冲突时如果哈希表未被装满则把key存放到冲突位置的“下一个”空位置中去。
1.1.1线性探测
线性探测找“下一个”空位置从发生冲突的位置开始依次向后探测“下一个”空位置。 线性探测的缺点 ①把更多冲突的元素聚集在一起这与其找下一个空位置有关 ②不能随便删除哈希表1中已有的元素如删除5则55查找起来可能会受影响
1.1.2二次探测
为了避免把更多冲突的元素聚集在一起二次探测找“下一个”空位置的方法为Hi (H0 i ^2) % capacity 或 Hi (H0 - i ^2) % capacity 与线性探测相比二次探测中冲突的元素较分开。 闭散列的缺点空间利用率较低也是哈希的缺陷。
1.2开散列
开散列法也叫链地址法/开链法使用哈希桶方式解决哈希冲突。哈希桶方式解决哈希冲突哈希表是数组链表的结构当链表的长度超过8 数组的长度超过64时链表变成红黑树。向哈希表中插入元素时JDK1.8之前是头插法JDK1.8之后是尾插法。
二、模拟实现哈希表
这里用了开散列法解决哈希冲突。
//key-value模型
class Person {public String id;public Person(String id) {this.id id;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Person person (Person) o;return Objects.equals(id, person.id);}Overridepublic int hashCode() {return Objects.hash(id);}
}
public class HashBucketK, V {private static class NodeK, V {private K key;private V val;Node next;public Node(K key, V value) {this.key key;this.val value;}}private NodeK, V[] array;private int usedSize;private static final double LOAD_FACTOR 0.75;private static final int DEFAULT_SIZE 8;//默认桶的大小public HashBucket() {array (NodeK, V[])new Node[10];}public void put(K key, V val) {int hash key.hashCode();int index hash % array.length;NodeK, V cur array[index];while(cur ! null) {if(cur.key.equals(key)) {cur.val val;return;}cur cur.next;}NodeK, V node new Node(key, val);//头插法node.next array[index];array[index] node;usedSize;if(loadFactor() LOAD_FACTOR) {resize();}}//扩容要把所有的元素重新进行哈希private void resize() {NodeK, V[] tmpArr new Node[array.length * 2];//遍历原来数组将原来数组的元素重新哈希到新的数组当中。因为要遍历原来的数组所以扩容时要申请一个新的数组for (int i 0; i array.length; i) {NodeK, V cur array[i];while(cur ! null) {NodeK, V curNext cur.next;int hash cur.key.hashCode();int newIndex hash % array.length;//头插法cur.next tmpArr[newIndex];tmpArr[newIndex] cur;cur curNext;}}array tmpArr;}private double loadFactor() {return usedSize * 1.0 / array.length;//散列表的载荷因子填入表中的元素个数/散列表的长度}public V get(K key) {int hash key.hashCode();int index hash % array.length;NodeK, V cur array[index];while (cur ! null) {if (cur.key.equals(key)) {return cur.val;}}return null;}
}三、HashMap源码的一些相关内容 HashMap的其中一个构造方法HashMap(int initialCapacity, float loadFactor)这个构造方法里面有一个tableSizeFor(int cap)方法tableSizeFor(int cap)方法的作用是返回一个接近目标容量的二次幂如HashMap(int initialCapacity, float loadFactor)中的initialCapacity给了1000则tableSizeFor(int cap)返回1024返回大于1000的不返回小于1000的。所以实例化HashMap时initialCapacity给了1000最后数组容量则是1024。 (h key.hashCode()) ^ (h 16)的目的是使关键字在哈希表中尽可能更均匀地分布。putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)中有(n - 1) hashn是数组长度当(n - 1)的值比较小时(n - 1)和hash二进制序列参与到计算中的只有低位。多个hash和(n - 1)进行计算如果hash和(n - 1)这两者的值的二进制序列均是低位相同高位不同的话(n - 1) hash计算出来的数组下标都是同一个增加了冲突的几率所以要用(h key.hashCode()) ^ (h 16)计算hash。当n是二次幂时hash%n和hash(n-1)的结果一样。的结果使二进制序列更向0集中|的结果使二进制序列更向1集中 ^的结果使二进制序列更加倾向保留参与计算的两者的二进制序列各自的特征。(h key.hashCode()) ^ (h 16)使hash的低位二进制序列既保留hashCode()二进制序列高位的特征又保留了hashCode()二进制序列低位的特征。
