如何創(chuàng)建Hash表

對于把K(鍵)-V(值)這樣的鍵值對插入Hash表中，需要執(zhí)行兩個(gè)步驟：

1.使用散列函數(shù)將K轉(zhuǎn)換為小整數(shù)(稱為其哈希碼)。

2.哈希碼用于查找索引(hashCode％arrSize)，并且首先搜索該索引處的整個(gè)鏈表(單獨(dú)鏈)以查找已存在的K。

3.如果找到，則更新其值，如果不是，則將K-V對存儲為列表中的新節(jié)點(diǎn)。

復(fù)雜性和負(fù)載因子

• 第一步，所用時(shí)間取決于K和散列函數(shù)。

例如，如果鍵是字符串“abcd”，那么它的散列函數(shù)可能取決于字符串的長度。 但是對于非常大的n值，與n相比，映射中的條目數(shù)，密鑰的長度幾乎可以忽略不計(jì)，因此可以認(rèn)為散列計(jì)算在恒定時(shí)間內(nèi)發(fā)生，即O(1)。

• 對于第二步，需要遍歷存在于該索引處的K-V對列表。 為此，最壞的情況可能是所有n個(gè)條目都在相同的索引處。 因此，時(shí)間復(fù)雜度將是O(n)。 但是，已經(jīng)進(jìn)行了足夠的研究以使散列函數(shù)產(chǎn)生的鍵在數(shù)組中均勻分布，因此這幾乎不會(huì)發(fā)生。

• 因此，平均而言，如果有n個(gè)條目且b是數(shù)組的大小，則每個(gè)索引上將有n / b個(gè)條目。 此值n / b稱為負(fù)載因子，表示hash表上的負(fù)載情況。

• 該負(fù)載因子(Load Factor)需要保持較低，因此一個(gè)索引處的條目數(shù)較少，因此復(fù)雜度幾乎恒定，即O(1)。

Rehashing

顧名思義，rehashing意味著再次散列。 基本上，當(dāng)負(fù)載因子增加到超過其預(yù)定值(負(fù)載因子的默認(rèn)值為0.75)時(shí)，復(fù)雜性就會(huì)增加。因此，為了克服這個(gè)問題，數(shù)組的大小增加(加倍)并且所有值再次進(jìn)行散列并存儲在新的雙倍大小的數(shù)組中，以保持低負(fù)載因子和低復(fù)雜度。

為什么要Rehashing

進(jìn)行重新散列是因?yàn)槊慨?dāng)將鍵值對插入到映射中時(shí)，負(fù)載因子增加，這意味著時(shí)間復(fù)雜度也如上所述地增加。 這可能無法提供O(1)所需的時(shí)間復(fù)雜度。

因此，必須進(jìn)行重新散列，增加Bucket Array的大小，以減少負(fù)載因子和時(shí)間復(fù)雜度。

如何Rehashing

可以按如下方式進(jìn)行Rehashing：

• 對于每次向hash表添加新條目，請檢查負(fù)載因子。
• 如果它大于其預(yù)定義值(如果沒有給出，則默認(rèn)值為0.75)，然后重新散列。
• 對于Rehashing，創(chuàng)建一個(gè)比以前大小加倍的新數(shù)組，并使其成為新的Bucket Array。
• 然后遍歷舊Bucket Array中的每個(gè)元素，并為每個(gè)元素調(diào)用insert()函數(shù)，以便將其插入到新的更大的bucket數(shù)組中。

Java程序?qū)嵗?/h1>// Java program to implement Rehashing import java.util.ArrayList; class Map { class MapNode { K key; V value; MapNode 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 stored ArrayList > buckets; // No. of pairs stored - n int size; // Size of the bucketArray - b int numBuckets; // Default loadFactor final double DEFAULT_LOAD_FACTOR = 0.75; public Map() { numBuckets = 5; buckets = new ArrayList<>(numBuckets); for (int i = 0; i < numBuckets; i++) { // Initialising to null buckets.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 + ""); } private int getBucketInd(K key) { // Using the inbuilt function from the object class int hashCode = key.hashCode(); // array index = hashCode%numBuckets return (hashCode % numBuckets); } public void insert(K key, V value) { // Getting the index at which it needs to be inserted int bucketInd = getBucketInd(key); // The first node at that index MapNode head = buckets.get(bucketInd); // First, loop through all the nodes present at that index // to check if the key already exists while (head != null) { // If already present the value is updated if (head.key.equals(key)) { head.value = value; return; } head = head.next; } // new node with the K and V MapNode newElementNode = new MapNode(key, value); // The head node at the index head = buckets.get(bucketInd); // the new node is inserted // by making it the head // and it's next is the previous head newElementNode.next = head; buckets.set(bucketInd, newElementNode); System.out.println("Pair(" + key +

總結(jié)

以上是生活随笔為你收集整理的如何动态的向数组中插入键值对_在Java中实现的一个简单“HashMap”的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。