Почему мой HashTable не допускает столкновения клавиш? - PullRequest
Новая
       34

Почему мой HashTable не допускает столкновения клавиш?

2 голосов
/ 20 августа 2011

Я прочитал, что HashTable может сопоставить один и тот же ключ с несколькими значениями. Вот что такое столкновение.

Теперь я запускаю программу так: 

Dictionary<String,String> hTable = new Hashtable<String,String>();
hTable.put("a", "aa");
hTable.put("a", "ab");
System.out.println(""+hTable.get("a"));

Мое мышление говорит, что я должен получить aa и ab.

Но фактический результат составляет ab

Почему это так? Где же тогда столкновение?

Ответы [ 5 ]

3 голосов
/ 20 августа 2011

Столкновение происходит только внутри .Для пользователя разрешено прозрачно.

Вот почему хеш-таблица может быть словарем - она ​​сопоставляет каждый ключ ровно 1 значению.Если он сопоставлен с более чем 1 значением, это не будет словарь.

3 голосов
/ 20 августа 2011

Нет столкновения.Запись HashTable отображает ключ только на одно значение.

Третья строка в вашем примере: 

hTable.put("a", "ab");

заменяет сопоставление с a на aa сопоставлением с a to ab.

После завершения выполнения четырех строк кода, hTable имеет только одно отображение: a на ab.

2 голосов
/ 20 августа 2011

HashTable - это ключ -> отображение значений.Это означает, что вы не можете иметь несколько значений для более одного ключа.Вам необходимо объединить две структуры данных, хранить несколько значений с одним ключом.

Например, вы можете поместить linkList в ваш HashTable.Например, 

HashTable<String,LinkedList<String>> table = new HashTable();
LinkedList<String> list = new LinkedList();
list.add("aa");
list.add("ab");
table.add("a",list);

теперь вы можете сделать это: получить значение aa и ab ; 

table.get("a").get(0); // returns aa
table.get("a").get(1); // returns ab

Я настоятельно рекомендую вам пройтиосновы структуры данных и алгоритма.

2 голосов
/ 20 августа 2011

Hashtable не отображает один и тот же ключ на несколько значений. Столкновение таково, что несколько ключей могут быть сопоставлены одному и тому же хеш-значению . Это решается самой структурой данных, которая прозрачна для вас.

Если вы хотите получить aa и ab с помощью hTable.get ("a"), вам нужно создать Dictionary<String,List<String>> и добавить список со значениями того же ключа.

В вашем коде 

hTable.put("a", "aa");
hTable.put("a", "ab");

Ключи одинаковые. Таким образом, вторая операция использовала «ab» для переопределения «aa». Вот почему вы получаете только «ab».

1 голос
/ 20 августа 2011

Вы хотите получить значения по их ключам. Массив служит для этой цели, но ограничен использованием целочисленных ключей и может занимать слишком много места (подумайте о хранении значений только в позициях 0 и 1000, вам нужно выделить весь массив для 2 элементов).

HashTables решает обе эти проблемы:

  • дисперсионная неинъективная функция , которая преобразует массив байтов переменной длины в массив байтов фиксированной длины. Это означает, что у вас есть хеш (bytes_1) == хеш (bytes_2), но это не происходит слишком часто , а если bytes_1 ~ bytes_2, то хэши разные;
  • индекс используемых хэшей . Если функция возвращает массив из 10 байтов, у вас есть 2 ^ 80 возможностей, поэтому вам нужно сохранить отсортированный список хэшей, с которыми вы уже сталкивались;
  • массив связанных списков . Индекс хэшей отображает хеш с позицией в массиве.

Столкновение означает, что два ключа имеют одинаковый хэш: map.put("key1", "value1"); map.put("key2", "value2") key1 и key2 могут оказаться в одном и том же связанном списке.

...