Quick Hash Table с использованием цепочек

Question

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

      /* hash string value return int */
      public int hashFunction(String D) {
          char[] Thing = D.toCharArray();
          for(int i=0; i < Thing.length; i++){
             index += Thing[i]; }
          return index % TABLE_SIZE;          
      }

      /* hash string value return void */
      public void hashFunction(String D) {
        char[] Thing = D.toCharArray();
        for(int i=0; i < Thing.length; i++){
         index += Thing[i];}
        int hash = index % TABLE_SIZE;
        if(table[hash] == null){
          table[hash] = new HashEntry( Level,  Value );
        }        
        else{
          table[hash].setNext(nd);
        }
      }

      /* miscellaneous code snippet */
      if(table[hash] == null){
        table[hash] = new HashEntry();
      }

      else if (Data.compareTo("VAR") == 0) {
          Data = inFile.next();   
            char[] Thing = Data.toCharArray();
            for(int i=0; i < Thing.length; i++){
            hash += Thing[i];}
            hash = hash % TABLE_SIZE;           
            hm.setIntoHashTable(hash);      
                Data = inFile.next();
                    if(Data.compareTo("=") == 0) {
                    Data = inFile.next();
                    int value = Integer.parseInt(Data);
                    hm.getIntoHashTable(he.setValue(value));
                }
      }

Answer 1

Ну, цепочка происходит, когда у вас есть столкновение в индексах.

Предположим, у вас есть TABLE_SIZE=10

Теперь вы должны хранить строку abc, так что вы получите хэш как 4

Теперь, когда ты собираешься хранить строки cba, вы в конечном итоге с тем же хешем 4

Так что теперь хранить cba по тому же индексу вы создадите и сохраните список по индексу 4,

Список будет содержать оба abc а также bca, Этот список называется chain и этот процесс хранения нескольких значений в одном хеше называется Chaining,

Псевдокод выглядит так:

if(table[hash] == null)
  table[hash] = new ArrayList<HashEntry>();//APPEND ON TO THE LOCATION ALREADY THERE!
table[hash].add(new HashEntry());

Таблица будет объявлена ​​как:

@SuppressWarnings("unchecked")
List<HashEntry>[] table = new List[TABLE_SIZE];

Возможно, вам придется подавить предупреждение, поскольку массивы и генерики не работают гладко.