Java実装の簡単なHashMap

Hashテーブルの作成方法
K(キー)-V(値)のようなキー値ペアをHashテーブルに挿入するには、2つのステップが必要です.

は、ハッシュ関数を使用してKを小さな整数(そのハッシュコードと呼ばれる)に変換する.

ハッシュコードは、インデックス(hashCode%arrSize)を検索するために使用され、最初にインデックスにおけるチェーンテーブル全体(単一チェーン)を検索して、既存のKを検索する.

が見つかった場合、その値が更新され、そうでない場合、K-Vペアがリスト内の新しいノードとして格納されます.

複雑さと負荷係数

最初のステップは、Kおよびハッシュ関数に依存して時間がかかる.

たとえば、キーが文字列「abcd」である場合、そのハッシュ関数は文字列の長さに依存する可能性があります.しかし,非常に大きなn値では,マッピング中のエントリ数に比べて鍵の長さはほとんど無視できるため,ハッシュ計算は一定時間,すなわちO(1)で起こると考えられる.

は、第2のステップについて、インデックスに存在するK−Vペアのリストを巡回する必要がある.このため、最悪の場合、すべてのn個のエントリが同じインデックスにある可能性があります.したがって,時間的複雑さはO(n)となる.しかし,ハッシュ関数で生成された結合が配列中に均一に分布するように十分な研究が行われているので,これはほとんど起こらない.

したがって、平均すると、n個のエントリがあり、bが配列のサイズである場合、各インデックスにはn/b個のエントリがある.この値n/bを負荷因子と呼び,hashテーブル上の負荷状況を表す.

負荷係数(Load Factor)は低く維持する必要があるため、1つのインデックスにおけるエントリ数が少ないため、複雑度はほぼ一定、すなわちO(1)である.

Rehashing
名前の通り、rehashingは再びハッシュすることを意味します.基本的には、負荷係数が所定値を超える(負荷係数のデフォルト値が0.75)まで増加すると、複雑さが増加する.従って、この問題を克服するために、配列のサイズが増加(倍増)し、すべての値が再びハッシュされ、低負荷因子と低複雑度を維持するために、新しい2倍サイズの配列に格納される.
なぜ?
再ハッシュは、キー値ペアがマッピングに挿入されるたびに負荷係数が増加するため、時間的複雑さも上述したように増加することを意味する.これはO(1)に要する時間的複雑さを提供できない可能性がある.
したがって,負荷因子と時間的複雑さを低減するためにBucket Arrayのサイズを大きくするために再ハッシュを行う必要がある.
どうやって?
Rehashingは次のように行えます.

hashテーブルに新しいエントリを追加するたびに、負荷係数を確認します.

事前定義値より大きい場合(指定されていない場合、デフォルト値は0.75)、再ハッシュされます.

Rehashingでは、以前のサイズよりも2倍の新しい配列を作成し、新しいBucket Arrayにします.

は、その後、古いBucket Arrayの各要素を巡回し、各要素に対してinsert()関数を呼び出して、新しいより大きなbucket配列に挿入します.

Javaプログラムインスタンス

// 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 + ", " + value + ") inserted successfully.
"); 

        // 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.
"); 

            // Rehash 
            rehash(); 

            System.out.println("New Size of Map: " + numBuckets + "
"); 
        } 

        System.out.println("Number of pairs in the Map: " + size); 
        System.out.println("Size of Map: " + numBuckets + "
"); 
    } 

    private void rehash() 
    { 

        System.out.println("
***Rehashing Started***
"); 

        // The present bucket list is made temp 
        ArrayList > temp = buckets; 

        // New bucketList of double the old size is created 
        buckets = new ArrayList >(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 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("
***Rehashing Ended***
"); 
    } 

    public void printMap() 
    { 

        // The present bucket list is made temp 
        ArrayList > 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 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 map = new Map(); 

        // 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

テキストリンク