Структурата на данните на Хеш таблицата

Относно серията #data-structures

Поредицата #data-structures е колекция от публикации за повторно внедрени структури от данни в JavaScript.

Ако не сте запознати със структурите от данни, кратко въведение и пълният списък на повторно внедрени структури от данни можете да намерите в въвеждащата публикация от поредицата за структури от данни в JavaScript.

Ако се чувствате добре с концепцията на всяка структура от данни и искате да видите само кода, погледнете обобщената публикация на поредицата. Той премахва всички обяснения и съдържа само JavaScript кода за всички структури от данни, обсъждан в поредицата.

Вземете кода от Github

Разбира се, целият код може да бъде намерен и в Github в хранилището data-structures-in-javascript.

Определение

Хеш таблица (хеш карта) е структура от данни, използвана за внедряване на асоциативен масив, структура, която може да съпоставя ключове със стойности. Хеш таблицата използва хеш функция за изчисляване на индекс в масив от кофи или слотове, от които може да бъде намерена желаната стойност. От Уикипедия

Хеш таблиците се считат за по-ефективната структура на данни за търсене и поради тази причина те се използват широко.

Сложност

Средно аритметично:

Достъп =› -, Търсене =› O(1), Вмъкване =› O(1), Изтриване =› O(1)

За да получите пълен преглед на времевата и пространствената сложност на структурата на данните на хеш-таблицата, вижте този отличен Big O cheat sheet.

Кодът

Тъй като функцията ми CalculateHash е прекалено проста (мода на дължината на ключа), трябва да съм сигурен, че мога да запазя повече от една стойност за всеки хеш. В резултат на това съхранявам друг обект за всеки хеш в моята хеш таблица.

По-добър пример би имал функция CalculateHash, която връща само един възможен хеш за всеки ключ. Можех да направя това с обикновен JavaScript обект (хешът е същият като ключа), но спецификата на структурата на данните на таблицата с хеширане е да има тази специална функция CalculateHash.

function HashTable(size) {
  this.values = {};
  this.numberOfValues = 0;
  this.size = size;
}
HashTable.prototype.add = function(key, value) {
  var hash = this.calculateHash(key);
  if(!this.values.hasOwnProperty(hash)) {
    this.values[hash] = {};
  }
  if(!this.values[hash].hasOwnProperty(key)) {
    this.numberOfValues++;
  }
  this.values[hash][key] = value;
};
HashTable.prototype.remove = function(key) {
  var hash = this.calculateHash(key);
  if(this.values.hasOwnProperty(hash) &&
      this.values[hash].hasOwnProperty(key)) {
    delete this.values[hash][key];
    this.numberOfValues — ;
  }
};
HashTable.prototype.calculateHash = function(key) {
  return key.toString().length % this.size;
};
HashTable.prototype.search = function(key) {
  var hash = this.calculateHash(key);
  if(this.values.hasOwnProperty(hash) &&
      this.values[hash].hasOwnProperty(key)) {
    return this.values[hash][key];
  } else {
    return null;
  }
};
HashTable.prototype.length = function() {
  return this.numberOfValues;
};
HashTable.prototype.print = function() {
  var string = ‘’;
  for(var value in this.values) {
    for(var key in this.values[value]) {
      string += this.values[value][key] + ‘ ‘;
    }
  }
  console.log(string.trim());
};
var hashTable = new HashTable(3);
hashTable.add(‘first’, 1);
hashTable.add(‘second’, 2);
hashTable.add(‘third’, 3);
hashTable.add(‘fourth’, 4);
hashTable.add(‘fifth’, 5);
hashTable.print(); // => 2 4 1 3 5
console.log(‘length gives 5:’, hashTable.length()); // => 5
console.log(‘search second gives 2:’, hashTable.search(‘second’)); // => 2
hashTable.remove(‘fourth’);
hashTable.remove(‘first’);
hashTable.print(); // => 2 3 5
console.log(‘length gives 3:’, hashTable.length()); // => 3

Първоначално публикувано в blog.benoitvallon.com.