Объяснение об алгоритме хеширования HashMap в этом примере - PullRequest
Новая
       47

Объяснение об алгоритме хеширования HashMap в этом примере

5 голосов
/ 04 октября 2019

Я пытался решить этот вопрос:

Учитывая массив целых чисел только с 3 уникальными числами, выведите числа в порядке возрастания (с соответствующими частотами) за O (n) раз.

Я хотел решить эту проблему, не используя алгоритм counting sort, поэтому я подумал, что могу просто сделать for loop и вставить числа в HashMap, а затем loop черезHashMap entrySet и выведите необходимую информацию.

Вот функция: 

public static void printOut(int[] arr){
        Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
        for(int num : arr){
            if(hm.containsKey(num)){
                hm.put(num,hm.get(num)+1);
            }else{hm.put(num,1);}
        }
        for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
            System.out.println("Key= "+entry.getKey()+" Value= "+entry.getValue());
        }
}

, которая добилась цели, когда мой массив был: [3, 3, 2, 1, 3, 2, 1]

ОднакоПриведенный выше массив не должен приводить к каким-либо коллизиям, поэтому я попытался использовать массив, который должен привести к коллизиям, один из массивов, с которыми я тестировал свою функцию, был: [6,6,9,9,6,3,9], но моя функция все еще печатала Keys в порядке возрастания, который получилменя смутило, потому что я думал, что когда Key из HashMap является целым числом, хэш-код должен быть hashIndex = key % noOfBuckets, поэтому, когда у меня есть числа 6, 9 and 3 в качестве моего HashMap keys, я думал, что будут столкновения и моя функцияследует напечатать (на основе указанного выше массива): 

Key= 6 Value= 3
Key= 9 Value= 3
Key= 3 Value= 1

Но вместо этого он напечатал: 

Key= 3 Value= 1
Key= 6 Value= 3
Key= 9 Value= 3

Может кто-нибудь объяснить мне, почему я получил правильное решение вопроса, который пыталсярешить вместо того ответа, который я ожидал?

Спасибо.

Ответы [ 6 ]

8 голосов
/ 07 октября 2019
  1. Термин "столкновение" в хэш-карте / хэш-таблице - это ситуация, когда два разных ключа имеют одинаковый хэш-код. Java-реализация HashMap использует List / RB-tree для разрешения коллизий, но если у вас есть буквально 3 целочисленных ключа, это определенно не ваш случай.
  2. HashMap не гарантирует порядок вставки (или любой другой) элементов. Существуют различные другие структуры, такие как LinkedHashMap или TreeMap, которые могут гарантировать некоторый порядок. Но использование этих структур для вашего случая немного сложнее, потому что вы можете отсортировать свою коллекцию из 3 элементов за постоянное время. Вы даже можете использовать массив Map.Entry вместо HashMap для вашей задачи.
3 голосов
/ 12 октября 2019

Это просто совпадение, и заказ от EntrySet и KeySet не гарантируется. Infact hashmap сам по себе не гарантирует порядок вставки, и этот порядок также может измениться во время перехеширования.

Теперь вы пытаетесь вставить примитив int в hashmap как ключ, который внутренне выполняет автобокс, и объект Integer будет вставлен как ключ.

Целочисленная хеш-кодовая функция 

public static int hashCode(int value) {
    return value;
}

Означает, что она просто возвращает непосредственно значение, в вашем случае 6,9 и 3

Тогда этот хеш-код используется внутренне хеш-картой длявычисление для получения позиции индекса 

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Как вы можете видеть, побитовый оператор с заданными значениями вернет 0, а экспоненциальное значение этих значений приведет к тому же порядковому значению индекса 3, что приведет к коллизии. Таким образом, hashmap сохранит его, используя LinkedList (ранее java8) и в дереве (java8 и его более поздние версии).

При выполнении итерации с помощью keySet или entrySet порядок не будет гарантирован, и поэтому порядок, которыйвы получаете просто совпадение.

3 голосов
/ 11 октября 2019

Как уже упоминалось выше в ответе @Serge Harnyk

HashMap не гарантирует порядок вставки (или любой другой) элементов.

Я запустилПриведенный выше код, которым вы поделились в вопросе с массивом [66,66,69,69,66,63,63,69], и вывод был 

Key= 66 Value= 3
Key= 69 Value= 3
Key= 63 Value= 2

Здесь вы можете видеть, что вывод не в отсортированном порядке. Другой массив, для которого entrySet () не возвращал элементы в отсортированном порядке, был [10,5,5,10,10,5,10000000]

Key= 5 Value= 3
Key= 10000000 Value= 1
Key= 10 Value= 3

Итак, как указано в документации HashMapпорядок элементов, возвращаемых entrySet () или keySet () HashMap, не гарантируется в порядке вставки / сортировки.

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

for(Map.Entry<Integer,Integer> entry : hm.entrySet()) {
    System.out.println("key= "+entry.getKey()+" has Hash Code= "+entry.getKey().hashCode()); 
}

Array [66,66,69,69,66,63,63,69] имел вывод 

key= 66 has Hash Code= 66
key= 69 has Hash Code= 69
key= 63 has Hash Code= 63

Массив [10,5,5,10,10,5,10000000] имел вывод 

key= 5 has Hash Code= 5
key= 10000000 has Hash Code= 10000000
key= 10 has Hash Code= 10

Из них видно, что для целочисленных ключей хеш-код не равен hashIndex = key % noOfBuckets. Кроме того, вы можете определить собственную реализацию метода hashCode () и использовать его против HashMap. Вы можете найти подробное объяснение реализации вашей пользовательской функции hashCode () здесь.

см. https://www.geeksforgeeks.org/internal-working-of-hashmap-java/

2 голосов
/ 07 октября 2019

Может ли кто-нибудь объяснить мне, почему я получил правильное решение вопроса, который я пытался решить вместо ответа, который я ожидал?

Это совпадение

ОБНОВЛЕНИЕ

Как уже упоминалось другими, HashMap не гарантирует какой-либо порядок при переборе содержимого, в отличие от TreeMap, который отсортирован, или LinkHashMap, который сохраняет порядок ввода. Так что да, если ваши элементы отсортированы, это просто совпадение.

0 голосов
/ 07 октября 2019

выдержка из Замечания по реализации для HashMap:

Корзины дерева (т.е. корзины, элементами которых являются все узлы дерева)упорядоченный главным образом по hashCode, , но в случае связей, если дваэлементы одного и того же «класса C реализует Comparable»,затем введите их метод сравнения для заказа.

Последующее относится к классу Integer: implements Comparable<Integer>.

Хеш-код Integer всегда является его целочисленным значением. И поскольку коллизия происходит только тогда, когда две разные записи получают один и тот же хэш-код, для целых чисел коллизий не будет. Порядок узлов в таблице зависит от хеш-кода. Может быть, целочисленные клавиши предварительно отсортированы?

0 голосов
/ 07 октября 2019

Я не уверен, что именно вы подразумеваете под "коллизиями", но, как уже указывалось, если вы читаете документацию по HashMap (https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html), нет никакого объявления о порядке:

"Этот класс не дает никаких гарантий относительно порядка карты, в частности он не гарантирует, что порядок будет оставаться постоянным во времени. "

И позже" Чтобы улучшить воздействие, когда ключи сравнимы, этокласс может использовать порядок сравнения между ключами, чтобы помочь разорвать связи. ".

Наконец, вы используете Integer как ключи, которые реализуют интерфейс Comparable, это означает, что реализация HashMap может упорядочить ихключи - это действительно так.

Вы также можете использовать реализацию Hash, где порядок ключей предопределен и для этого предсказуем, как SortedMap.

...