Query - объяснение функции HashCode - PullRequest
Новая
       10

Query - объяснение функции HashCode

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

Мне трудно понять, как работает хэш-код моего профессора, использованный в прошлой экзаменационной работе. Я хотел бы уточнить следующее:

1 - Какой тип техники хеширования используется для обнаружения столкновений и как функция «HashCode» обрабатывает столкновения?

  • Я попробовал приведенную ниже формулу, чтобы выяснить, где находится набор, но я получал ответы, отличные от программы (например, h ("cc") = 6% 16 = 6 [16емкость по умолчанию для HashSet], хотя предполагается, что она равна 12 (двойное хеширование используется для перехода 6, кажется), но h ("bb") также равно 6). Я не уверен, какой тип хеширования используется для преодоления столкновений, есть ли у меня какой-либо способ узнать?

Вопрос:

Предположим, что хеш-функция: ? (???) = ???. ???????? ()% ??. factor, коэффициент загрузки 0,75 и отдельное изменение используются в программе выше. Если вставка нового элемента приведет к тому, что отношение размера / емкости будет больше, чем коэффициент загрузки, тогда размер hs удваивается, и перед вставкой этого нового элемента запускается повторное хеширование. Нарисуйте диаграммы, которые иллюстрируют емкость и содержимое hs сразу после каждого оператора, который вставляет новый элемент в hs. 

import java.util.*;

public class HashStringDemo{
 public static void main(String[] args){
 HashSet<MyString> hs = new HashSet<>(2);
 MyString s1=new MyString("aa"),s2=new MyString("ab");
 MyString s3=new MyString("bb"),s4=new MyString("cc");

 hs.add(s1);
 hs.add(s2);
 hs.add(s3);
 hs.add(s4);
 }
}
class MyString{
 private String s;
 public MyString(String s){
 this.s=s;
 }
 public boolean equals(Object o){
 if (!(o instanceof MyString))
 return false;
 MyString s1 = (MyString)o;
 return s.equals(s1.s);
 }
 public int hashCode(){
 int sum=0;
 for(int i=0;i<s.length();i++){
 sum+=(s.charAt(i)-'a')*Math.pow(2,s.length()-i);
 }
 return sum;
 }
 public String toString(){ return s; }
}

Результаты (при вызове функции 'HashCode') с использованием Eclipse IDE: 

aa : 0
ab : 2
bb : 6
cc : 12
...