转载

Java实现的一个简单HashMap（翻译）

如何创建Hash表

对于把K（键）-V（值）这样的键值对插入Hash表中，需要执行两个步骤：

使用散列函数将K转换为小整数（称为其哈希码）。
哈希码用于查找索引（hashCode％arrSize），并且首先搜索该索引处的整个链表（单独链）以查找已存在的K。
如果找到，则更新其值，如果不是，则将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 Rehashing 

import 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 stored 
    ArrayList<MapNode<K, V> > 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 + "/n"); 
    } 

    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<K, V> 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<K, V> newElementNode = new MapNode<K, V>(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 + ", " + value + ") inserted successfully./n"); 

        // Incrementing size 
        // as new K-V pair is added to the map 
        size++; 

        // Load factor calculated 
        double loadFactor = (1.0 * size) / numBuckets; 

        System.out.println("Current Load factor = " + loadFactor); 

        // If the load factor is > 0.75, rehashing is done 
        if (loadFactor > DEFAULT_LOAD_FACTOR) { 
            System.out.println(loadFactor + " is greater than " + DEFAULT_LOAD_FACTOR); 
            System.out.println("Therefore Rehashing will be done./n"); 

            // Rehash 
            rehash(); 

            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 temp 
        ArrayList<MapNode<K, V> > temp = buckets; 

        // New bucketList of double the old size is created 
        buckets = new ArrayList<MapNode<K, V> >(2 * numBuckets); 

        for (int i = 0; i < 2 * numBuckets; i++) { 
            // Initialised to null 
            buckets.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 list 
        size = 0; 
        numBuckets *= 2; 

        for (int i = 0; i < temp.size(); i++) { 

            // head of the chain at that index 
            MapNode<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 bucketArray 
                insert(key, val); 
                head = head.next; 
            } 
        } 

        System.out.println("/n***Rehashing Ended***/n"); 
    } 

    public void printMap() 
    { 

        // The present bucket list is made temp 
        ArrayList<MapNode<K, V> > temp = buckets; 

        System.out.println("Current HashMap:"); 
        // loop through all the nodes and print them 
        for (int i = 0; i < temp.size(); i++) { 

            // head of the chain at that index 
            MapNode<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 Map 
        Map<Integer, String> map = new Map<Integer, String>(); 

        // Inserting elements 
        map.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 created
Number of pairs in the Map: 0
Size of Map: 5
Default Load Factor : 0.75

Pair(1, Geeks) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 1
Size of Map: 5

Current HashMap:
key = 1, val = Geeks

Pair(2, forGeeks) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 2
Size of Map: 5

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks

Pair(3, A) inserted successfully.

Current Load factor = 0.6
Number of pairs in the Map: 3
Size of Map: 5

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks
key = 3, val = A

Pair(4, Computer) inserted successfully.

Current Load factor = 0.8
0.8 is greater than 0.75
Therefore Rehashing will be done.


***Rehashing Started***

Pair(1, Geeks) inserted successfully.

Current Load factor = 0.1
Number of pairs in the Map: 1
Size of Map: 10

Pair(2, forGeeks) inserted successfully.

Current Load factor = 0.2
Number of pairs in the Map: 2
Size of Map: 10

Pair(3, A) inserted successfully.

Current Load factor = 0.3
Number of pairs in the Map: 3
Size of Map: 10

Pair(4, Computer) inserted successfully.

Current Load factor = 0.4
Number of pairs in the Map: 4
Size of Map: 10


***Rehashing Ended***

New Size of Map: 10

Number of pairs in the Map: 4
Size of Map: 10

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks
key = 3, val = A
key = 4, val = Computer

Pair(5, Portal) inserted successfully.

Current Load factor = 0.5
Number of pairs in the Map: 5
Size of Map: 10

Current HashMap:
key = 1, val = Geeks
key = 2, val = forGeeks
key = 3, val = A
key = 4, val = Computer
key = 5, val = Portal

原文链接

原文 https://segmentfault.com/a/1190000020254131

正文到此结束