如何创建Hash表

对于把K(键)-V(值)这样的键值对插入Hash表中,需要执行两个步骤:

1.使用散列函数将K转换为小整数(称为其哈希码)。

2.哈希码用于查找索引(hashCode%arrSize),并且首先搜索该索引处的整个链表(单独链)以查找已存在的K。

3.如果找到,则更新其值,如果不是,则将K-V对存储为列表中的新节点。

复杂性和负载因子

第一步,所用时间取决于K和散列函数。

例如,如果键是字符串“abcd”,那么它的散列函数可能取决于字符串的长度。 但是对于非常大的n值,与n相比,映射中的条目数,密钥的长度几乎可以忽略不计,因此可以认为散列计算在恒定时间内发生,即O(1)。

对于第二步,需要遍历存在于该索引处的K-V对列表。 为此,最坏的情况可能是所有n个条目都在相同的索引处。 因此,时间复杂度将是O(n)。 但是,已经进行了足够的研究以使散列函数产生的键在数组中均匀分布,因此这几乎不会发生。因此,平均而言,如果有n个条目且b是数组的大小,则每个索引上将有n / b个条目。 此值n / b称为负载因子,表示hash表上的负载情况。该负载因子(Load Factor)需要保持较低,因此一个索引处的条目数较少,因此复杂度几乎恒定,即O(1)。

Rehashing

顾名思义,rehashing意味着再次散列。 基本上,当负载因子增加到超过其预定值(负载因子的默认值为0.75)时,复杂性就会增加。因此,为了克服这个问题,数组的大小增加(加倍)并且所有值再次进行散列并存储在新的双倍大小的数组中,以保持低负载因子和低复杂度。

为什么要Rehashing

进行重新散列是因为每当将键值对插入到映射中时,负载因子增加,这意味着时间复杂度也如上所述地增加。 这可能无法提供O(1)所需的时间复杂度。

因此,必须进行重新散列,增加Bucket Array的大小,以减少负载因子和时间复杂度。

如何Rehashing

可以按如下方式进行Rehashing:

对于每次向hash表添加新条目,请检查负载因子。如果它大于其预定义值(如果没有给出,则默认值为0.75),然后重新散列。对于Rehashing,创建一个比以前大小加倍的新数组,并使其成为新的Bucket Array。然后遍历旧Bucket Array中的每个元素,并为每个元素调用insert()函数,以便将其插入到新的更大的bucket数组中。

Java程序实例

// Java program to implement Rehashingimport java.util.ArrayList;class Map<K, V> {class MapNode<K, V> {K key;V value;MapNode<K, V> next;public MapNode(K key, V value){this.key = key;this.value = value;next = null;}}// The bucket array where// the nodes containing K-V pairs are storedArrayList<MapNode<K, V> > buckets;// No. of pairs stored - nint size;// Size of the bucketArray - bint numBuckets;// Default loadFactorfinal double DEFAULT_LOAD_FACTOR = 0.75;public Map(){numBuckets = 5;buckets = new ArrayList<>(numBuckets);for (int i = 0; i < numBuckets; i++) {// Initialising to nullbuckets.add(null);}System.out.println("HashMap created");System.out.println("Number of pairs in the Map: " + size);System.out.println("Size of Map: " + numBuckets);System.out.println("Default Load Factor : " + DEFAULT_LOAD_FACTOR + "\n");}private int getBucketInd(K key){// Using the inbuilt function from the object classint hashCode = key.hashCode();// array index = hashCode%numBucketsreturn (hashCode % numBuckets);}public void insert(K key, V value){// Getting the index at which it needs to be insertedint bucketInd = getBucketInd(key);// The first node at that indexMapNode<K, V> head = buckets.get(bucketInd);// First, loop through all the nodes present at that index// to check if the key already existswhile (head != null) {// If already present the value is updatedif (head.key.equals(key)) {head.value = value;return;}head = head.next;}// new node with the K and VMapNode<K, V> newElementNode = new MapNode<K, V>(key, value);// The head node at the indexhead = buckets.get(bucketInd);// the new node is inserted// by making it the head// and its next is the previous headnewElementNode.next = head;buckets.set(bucketInd, newElementNode);System.out.println("Pair(" + key + ", " + value + ") inserted successfully.\n");// Incrementing size// as new K-V pair is added to the mapsize++;// Load factor calculateddouble loadFactor = (1.0 * size) / numBuckets;System.out.println("Current Load factor = " + loadFactor);// If the load factor is > 0.75, rehashing is doneif (loadFactor > DEFAULT_LOAD_FACTOR) {System.out.println(loadFactor + " is greater than " + DEFAULT_LOAD_FACTOR);System.out.println("Therefore Rehashing will be done.\n");// Rehashrehash();System.out.println("New Size of Map: " + numBuckets + "\n");}System.out.println("Number of pairs in the Map: " + size);System.out.println("Size of Map: " + numBuckets + "\n");}private void rehash(){System.out.println("\n***Rehashing Started***\n");// The present bucket list is made tempArrayList<MapNode<K, V> > temp = buckets;// New bucketList of double the old size is createdbuckets = new ArrayList<MapNode<K, V> >(2 * numBuckets);for (int i = 0; i < 2 * numBuckets; i++) {// Initialised to nullbuckets.add(null);}// Now size is made zero// and we loop through all the nodes in the original bucket list(temp)// and insert it into the new listsize = 0;numBuckets *= 2;for (int i = 0; i < temp.size(); i++) {// head of the chain at that indexMapNode<K, V> head = temp.get(i);while (head != null) {K key = head.key;V val = head.value;// calling the insert function for each node in temp// as the new list is now the bucketArrayinsert(key, val);head = head.next;}}System.out.println("\n***Rehashing Ended***\n");}public void printMap(){// The present bucket list is made tempArrayList<MapNode<K, V> > temp = buckets;System.out.println("Current HashMap:");// loop through all the nodes and print themfor (int i = 0; i < temp.size(); i++) {// head of the chain at that indexMapNode<K, V> head = temp.get(i);while (head != null) {System.out.println("key = " + head.key + ", val = " + head.value);head = head.next;}}System.out.println();}}public class GFG {public static void main(String[] args){// Creating the MapMap<Integer, String> map = new Map<Integer, String>();// Inserting elementsmap.insert(1, "Geeks");map.printMap();map.insert(2, "forGeeks");map.printMap();map.insert(3, "A");map.printMap();map.insert(4, "Computer");map.printMap();map.insert(5, "Portal");map.printMap();}}

运行输出

HashMap createdNumber of pairs in the Map: 0Size of Map: 5Default Load Factor : 0.75Pair(1, Geeks) inserted successfully.Current Load factor = 0.2Number of pairs in the Map: 1Size of Map: 5Current HashMap:key = 1, val = GeeksPair(2, forGeeks) inserted successfully.Current Load factor = 0.4Number of pairs in the Map: 2Size of Map: 5Current HashMap:key = 1, val = Geekskey = 2, val = forGeeksPair(3, A) inserted successfully.Current Load factor = 0.6Number of pairs in the Map: 3Size of Map: 5Current HashMap:key = 1, val = Geekskey = 2, val = forGeekskey = 3, val = APair(4, Computer) inserted successfully.Current Load factor = 0.80.8 is greater than 0.75Therefore Rehashing will be done.***Rehashing Started***Pair(1, Geeks) inserted successfully.Current Load factor = 0.1Number of pairs in the Map: 1Size of Map: 10Pair(2, forGeeks) inserted successfully.Current Load factor = 0.2Number of pairs in the Map: 2Size of Map: 10Pair(3, A) inserted successfully.Current Load factor = 0.3Number of pairs in the Map: 3Size of Map: 10Pair(4, Computer) inserted successfully.Current Load factor = 0.4Number of pairs in the Map: 4Size of Map: 10***Rehashing Ended***New Size of Map: 10Number of pairs in the Map: 4Size of Map: 10Current HashMap:key = 1, val = Geekskey = 2, val = forGeekskey = 3, val = Akey = 4, val = ComputerPair(5, Portal) inserted successfully.Current Load factor = 0.5Number of pairs in the Map: 5Size of Map: 10Current HashMap:key = 1, val = Geekskey = 2, val = forGeekskey = 3, val = Akey = 4, val = Computerkey = 5, val = Portal

文章最后,希望大家能看懂

我是小Jia,我们下篇文章见!

最后,小编整理一些关于分布式,微服务,性能优化,Spring,MyBatis的等源码知识点的录像视频。还有各种面试题的问题及答案哦。需要领取的话看我专栏介绍哦。

分类: 百科知识 标签: 暂无标签

评论

暂无评论数据

暂无评论数据

目录