Коэффициент нагрузки и повторное хеширование

Опубликовано: 24 Января, 2022

Предварительные требования: Введение в хеширование и обработка конфликтов путем отдельного объединения в цепочку.

Как работает хеширование:

Для вставки пары ключ (K) - значение (V) в хеш-карту требуется 2 шага:

  1. K преобразуется в небольшое целое число (называемое его хеш-кодом) с помощью хеш-функции.
  2. Хэш-код используется для поиска индекса (hashCode% arrSize), и сначала выполняется поиск всего связанного списка по этому индексу (отдельная цепочка) на наличие K уже.
  3. Если он найден, его значение обновляется, а если нет, пара KV сохраняется как новый узел в списке.

Сложность и коэффициент загрузки

  • Для первого шага затраченное время зависит от K и хэш-функции.
    Например, если ключ представляет собой строку «abcd», то ее хеш-функция может зависеть от длины строки. Но для очень больших значений n количество записей в карте, длина ключей почти ничтожна по сравнению с n, поэтому можно считать, что вычисление хеш-функции происходит в постоянное время, то есть за O (1) .
  • На втором этапе необходимо выполнить обход списка пар KV, присутствующих в этом индексе. Для этого наихудший случай может заключаться в том, что все n записей имеют один и тот же индекс. Таким образом, временная сложность будет O (n) . Но было проведено достаточно исследований, чтобы заставить хэш-функции равномерно распределять ключи в массиве, поэтому этого почти никогда не происходит.
  • Итак, в среднем , если имеется n записей, а b - размер массива, в каждом индексе будет n / b записей. Это значение n / b называется коэффициентом загрузки, который представляет нагрузку, которая присутствует на нашей карте.
  • Этот коэффициент загрузки необходимо поддерживать на низком уровне, чтобы количество записей в одном индексе было меньше, а сложность была почти постоянной, т. Е. O (1).

Перефразируя:

Как следует из названия, повторное хеширование означает повторное хеширование . В основном, когда коэффициент нагрузки увеличивается до значения, превышающего его предварительно определенное значение (значение коэффициента нагрузки по умолчанию составляет 0,75), сложность возрастает. Таким образом, чтобы преодолеть это, размер массива увеличивается (удваивается), и все значения снова хешируются и сохраняются в новом массиве двойного размера, чтобы поддерживать низкий коэффициент загрузки и низкую сложность.

Зачем перефразировать?

Повторное хеширование выполняется, потому что всякий раз, когда пары ключ-значение вставляются в карту, коэффициент загрузки увеличивается, что означает, что временная сложность также увеличивается, как описано выше. Это может не дать требуемой временной сложности O (1).

Следовательно, необходимо выполнить повторное хеширование, увеличив размер bucketArray, чтобы уменьшить коэффициент загрузки и временную сложность.

Как делается перехеширование?

Rehashing can be done as follows:

  • For each addition of a new entry to the map, check the load factor.
  • If it’s greater than its pre-defined value (or default value of 0.75 if not given), then Rehash.
  • For Rehash, make a new array of double the previous size and make it the new bucketarray.
  • Then traverse to each element in the old bucketArray and call the insert() for each so as to insert it into the new larger bucket array.

Program to implement Rehashing:

// 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 + " ");
    }
  
    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. ");
  
        // 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<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(" ***Rehashing Ended*** ");
    }
  
    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();
    }
}
Output:
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

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022