散列表
散列函数
- MD5
- SHA-1
实现散列表
散列表中的冲突
- 分离链接
- 线性探查
  - 线性探查的原理
  - 线性探查的实现
    - 挪动位置
    - 软删除

散列表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列表的一个常见应用是使用散列表来表示对象。JavaScript 语言内部就是使用散列表来表示每个对象。此时，对象的每个属性和方法 (成员) 被存储为 key 对象类型，每个 key 指向对应的对象成员。

散列函数

散列函数，又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字 “指纹” 的方法。简单的说就是一种将任意长度的输入值转变成固定长度的输出值的函数。其中输出值称为散列值，它通常是用一个短的随机字母和数字组成的字符串来表示。常用的散列函数有MD5、SHA-1 等。

MD5

MD5信息摘要算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。

SHA-1

SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法1）是一种密码散列函数，SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

实现散列表

定义 ValuePair 类

class ValuePair {
    constructor(key, value) {
      this.key = key;
    this.value = value;
  }
  toString() {
      const key = typeof this.key === 'object' ? JSON.stringify(this.key) : this.key;
    return `[#${key}: ${this.value}]`;
  }
}

ValuePair 类将原始的 key 和 value 转换成字符串，便于我们同时将原始的 key 和 value 保存在字典中

定义 defaultToString 函数

const defaultToString = (item) => {
    if (item === null) {
   return 'NULL';
  } else if (item === 'undefined') {
      return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
      return `${item}`;
  } else if (typeof item === 'object') {
      return JSON.stringify(item);
  }
  return item.toString();
}

JavaScript 的对象 (Object) ，本质上是键值对的集合 (Hash 结构)，传统上只能使用字符串作为键。因此，我们需要定义一个转换函数，将所有作为键名传入的对象转化为字符串，使得从 HashTable 类中搜索和获取值更简单。

定义 HashTable 类

class HashTable {
    constructor(toStrFn = defaultToString) {
      this.toStrFn = toStrFn;
    this.table = {};
  }
}

在 HashTable 类中，我们使用 Object 的实例来存储散列表中健值。

下面，我们为散列表定义一些可用的方法：

loseloseHashCode(key) 将 key 生成散列值
hashCode(key) 将 key 生成散列值
put(key, value) 将键和值加入散列表
remove(key) 从散列表中移除一个值
get(key) 从散列表中获取一个值
getTable() 获取整个散列表对象
isEmpty() 判断散列表是否为空
size() 返回散列表中的健值数量
clear() 清空散列表
toString() 将散列表转换成字符串并返回

下面，我们逐一实现散列表的方法：

loseloseHashCode 将 key 生成散列值

loseloseHashCode(key) {
  // key 是 number 类型，直接将其返回
    if (typeof key === 'number') {
      return key;
  }
  // 将key转换成字符串
  const tableKey = this.toStrFn(key);
  // hash 值
  let hash = 0;
  // 遍历字符串，将每个字符转换成 ASCII 值
  for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i)
  }
  // 返回一个较小数值的 hash 值
  return hash % 37;
}

在 loseloseCode 方法中，我们首先检验 key 是否是 number 类型的值，如果是，则直接将其返回。然后，我们将 key 转换成字符串，根据组成 key 的每个字符的 ASCII 码值组合成一个 hash 值。为了得到较小的数值，我们会用 hash 值和一个任意数做除法的余数（%）——这样可以规避操作数超过数值变量最大表示范围的风险。

hashCode 将 key 生成散列值

hashCode(key) {
    return this.loseloseHashCode(key);
}

hashCode 方法简单地调用了 loseloseHashCode 方法，将 key 作为参数传入。

put 将键和值加入散列表

put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
    this.table[position] = new ValuePair(key, value);
    return true;
  }
  return false;
}

put 方法会将键和值添加到散列表中。

首先，我们会检验 key 和 value 是否合法，如果不合法就直接返回 false，表示这个值没有被添加（更新）到散列表中。

key 和 value 是合法的，则根据 key 参数，使用 hashCode 函数在表中找到一个位置，然后用 key 和 value 创建一个 ValuePair 实例，将原始的 key 和 value 保存到这个位置上。

remove 从散列表中移除一个值

remove(key) {
  // 获取 hash 值，即在表中的位置
    const hash = this.hashCode(key);
  // 获取 hash 位置的存储的原始 key 和 value
  const valuePair = this.table[hash];
  if (valuePair != null) {
    // Reflect.deleteProperty方法等同于delete obj[name]，用于删除对象的属性
      // delete this.table[hash];
    Reflect.deleteProperty(this.table, hash);
    return true;
  }
  return false;
}

要从 HashTable 中移除一个值，首先需要知道值所在的位置，因此我们使用 hashCode 函数来获取 hash。我们在 hash 的位置获取到 valuePair，如果 valuePair 不是 null 或undefined，我们就将其删除。返回 true，表示删除成功，返回 false，表示没有从散列表中移除值。

get 从散列表中获取一个值

get(key) {
  const hash = this.hashCode(key)
    const valuePair = this.table[hash];
  return valuePair == null ? undefined : valuePair.value;
}

我们首先使用 hashCode 函数获取 key 参数的位置，然后从表中对应的位置获取到值并返回。

getTable 获取整个散列表对象

getTalbe() {
    return this.table;
}

isEmpty 判断散列表是否为空

isEmpty() {
    return this.size() === 0;
}

size 返回散列表中的健值数量

size() {
    return Object.keys(this.table).length;
}

clear 清空散列表

clear() {
    this.table = {};
}

toString 将散列表转换成字符串并返回

toString() {
  if (this.isEmpty()) {
      return '';
  }
    const keys = Object.keys(this.table);
  let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `{${objString}, ${[keys[i]]} => ${this.table[keys[i]].toString()}}`
  }
  return objString;
}

完整代码

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    const key = typeof this.key === 'object' ? JSON.stringify(this.key) : this.key;
    return `[#${key}: ${this.value}]`;
  }
}
const defaultToString = (item) => {
  if (item === null) {
    return 'NULL';
  } else if (item === 'undefined') {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  } else if (typeof item === 'object') {
    return JSON.stringify(item);
  }
  return item.toString();
}
class HashTable {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
  // 将 key 转换成 hash
  loseloseHashCode(key) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }
  // 将 key 转换成 hash
  hashCode(key) {
    return this.loseloseHashCode(key);
  }
  // 将键和值加入到散列表中
  put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      this.table[position] = new ValuePair(key, value);
      return true;
    }
    return false;
  }
  // 从散列表总获取一个值
  get(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    return valuePair == null ? undefined : valuePair.value;
  }
  // 从散列表中移除一个值
  remove(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair != null) {
      Reflect.deleteProperty(this.table, hash);
      return true;
    }
    return false;
  }
  // 获取整个散列表对象
  getTable() {
    return this.table;
  }
  // 判断散列表是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 返回散列表中的元素个数
  size() {
    return Object.keys(this.table).length;
  }
  // 清空散列表
  clear() {
    this.table = {};
  }
  // 将散列表转换成字符串并将其返回
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString}, {${keys[i]} => ${this.table[keys[i]].toString()}}`
    }
    return objString;
  }
}

散列表中的冲突

有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。例如，我们看下面的代码会输出怎样的结果：

const hashTable = new HashTable();
hashTable.put('Ygritte', 'ygritte@email.com')
hashTable.put('Jonathan', 'Jonathan@email.com')
hashTable.put('Jamie', 'Jamie@email.com')
hashTable.put('Jack', 'Jack@email.com')
hashTable.put('Jasmine', 'Jasmine@email.com')
hashTable.put('Jake', 'Jake@email.com')
hashTable.put('Nathan', 'Nathan@email.com')
hashTable.put('Athelstan', 'Athelstan@email.com')
hashTable.put('Sue', 'Sue@email.com')
hashTable.put('Aethelwulf', 'Aethelwulf@email.com')
hashTable.put('Sargeras', 'Sargeras@email.com')

通过对每个提到的名字调用 HashTable.hashCode 方法：

console.log(hashTable.hashCode('Ygritte') + ' - Ygritte')
console.log(hashTable.hashCode('Jonathan') + ' - Jonathan')
console.log(hashTable.hashCode('Jamie') + ' - Jamie')
console.log(hashTable.hashCode('Jack') + ' - Jack')
console.log(hashTable.hashCode('Jasmine') + ' - Jasmine')
console.log(hashTable.hashCode('Jake') + ' - Jake')
console.log(hashTable.hashCode('Nathan') + ' - Nathan')
console.log(hashTable.hashCode('Athelstan') + ' - Athelstan')
console.log(hashTable.hashCode('Sue') + ' - Sue')
console.log(hashTable.hashCode('Aethelwulf') + ' - Aethelwulf')
console.log(hashTable.hashCode('Sargeras') + ' - Sargeras')

输入结果如下：

4 - Ygritte
5 - Jonathan
5 - Jamie
7 - Jack
8 - Jasmine
9 - Jake
10 - Nathan
7 - Athelstan
5 - Sue
5 - Aethelwulf
10 - Sargeras

可见，Jonathan、Jamie、Sue 和 Aethelwulf 有相同的散列值 (5)，Jack 和 Athelstan 有相同的散列值 (7)，Nathan 和 Sargeras 也有相同的散列值 (10)。

那么，将这些名字添加到散列表中，结果会怎样呢？

我们执行 hashTable.toString() 方法来查看散列表中的值，如下：

console.log(hashTable.toString())
{4 => [#Ygritte: ygritte@email.com]},
{5 => [#Aethelwulf: Aethelwulf@email.com]},
{7 => [#Athelstan: Athelstan@email.com]},
{8 => [#Jasmine: Jasmine@email.com]},
{9 => [#Jake: Jake@email.com]},
{10 => [#Sargeras: Sargeras@email.com]}

我们发现，具有相同散列值的名字，被最后添加的名字给覆盖了。这显然不是我们想要的结果，我们使用一个数据结构来保存数据，其目的是要把它们全部保存起来，而不是会丢失数据。

那么我们如何解决散列冲突问题呢？

解决散列冲突的方法有很多，这里我们介绍分离链接和线性探查两种方法。

分离链接

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在链表里面。它是解决散列冲突的最简单的方法，但缺点是在 HashTable 实例之外还需要额外的存储空间。

下面，我们使用代码来实现分离链接法。

创建 HashTableSeparateChaining 类

class HashTableSeparateChaining {
    constructor(toStrFn = defaultToString) {
      this.toStrFn = toStrFn;
    this.table = {};
  }
}

对于分离链接来说，我们只需要重写 put、get、remove 三个方法即可。

put 将键和值加入散列表

put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
    if (this.table[position] == null) {
        this.table[position] =  new LinkedList();
    }
    this.table[position].push(new ValuePair(key, value));
    return true;
  }
  return false;
}

在 put 方法中，我们首先验证要加入新元素的位置是否已经被占据，如果是第一次向该位置加入元素，我们会在该位置上初始化一个 LinkedList 的实例，然后用 LinkedList 实例的 push 方法将键和值添加到 LinkedList 实例中。

get 从散列表中获取一个值

get(key) {
    const position = this.hashCode(key);
  // 获取 position 位置上的 LinkedList 实例
  const linkedList = this.table[position];
  // 判断 position 位置上是否有 LinkedList 实例
  if (linkedList != null && !linkedList.isEmpty()) {
    // 获取链表的头部元素
      let current = linkedList.head();
    // 迭代链表，寻找我们需要的元素
    while(current != null) {
      // 链表的节点的数据域 element 上存储的是 valuePair 实例，即原始的 健/值
        if (current.element.key === key) {
          return current.element.value;
      }
      // 继续迭代链表，访问下一个节点
      current = current.next;
    }
  }
  return undefined;
}

在 get 方法中，我们首先在 position 位置上检索是否存在 LinkedList 实例，如果没有，则返回 undefined 表示在 HashTable 中没有找到这个值。如果在 position 位置上有值存在，我们知道这是一个 LinkedList 实例，然后我们迭代这个链表来寻找我们需要的元素。

LinkedList 链表包含 element 属性和 next 指针，而 element 属性存储的是 ValuePair 实例，即 {key, value}，因此 element 属性有 value 属性和 key 属性。我们可以通过 current.element.key 来获取链表中节点的 key 属性，并通过比较它来确定它是否就是我们要找的键，如果 key 值相同，就返回存储在节点里的 value 值，如果 key 不相同，则继续迭代链表，访问下一个节点： current = current.next 。

remove 从散列表中移除一个值

remove(key) {
  // 生成 key 在 散列表中的位置
    const position = this.hashCode(key);
  // 获取 position 位置上的 LinkedList 实例
  const linkedList = this.table[position];
  // 如果 position 位置上 LinkedList 实例存在并且 LinkedList 实例不为空
  if (linkedList != null && !linkedList.isEmpty()) {
    // 链表头节点
      let current = linkedList.head();
    // 从链表头节点开始迭代链表，查找需要移除的值
    while(current != null) {
        if (current.element.key === key) {
        // 移除当前 key 在链表上的节点
          linkedList.remove(current.element);
        // 如果此时 链表为空，移除在 position 位置上的链表
        if (linkedList.isEmpty()) {
            // delete this.table[position];
          Reflect.deleteProperty(this.table, position);
        }
        return true
      }
      // 不是要移除的值，继续迭代下一个元素
      current = current.next;
    }
  }
  // 返回 false 表示没有从散列表中移除值
  return false;
}

在 remove 方法中，我们首先根据 key 生成的 hash 在散列表中查找该 hash 值对应位置上 LinkedList 实例。如果在该位置上没有 LinkedList 实例，我们会返回 false，表示没有从散列表中移除值。如果该位置上存在 LinkedList 实例，并且该 LinkedList 实例不为空，我们就从链表的头节点开始迭代链表，查找需要删除的值，如果在链表上找到了我们要删除的值，我们就将该值从链表中删除，并检查此时的链表是否是空链表，如果是空链表，就将该 hash 值对应位置上的 LinkedList 实例移除。最后返回 true，表示从散列表中移除值成功。

完整代码

LinkedList 类完整代码请参考数据结构与算法学习之链表一文。

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    const key = typeof this.key === 'object' ? JSON.stringify(this.key) : this.key;
    return `[#${key}: ${this.value}]`;
  }
}
const defaultToString = (item) => {
  if (item === null) {
    return 'NULL';
  } else if (item === 'undefined') {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  } else if (typeof item === 'object') {
    return JSON.stringify(item);
  }
  return item.toString();
}
class HashTableSeparateChaining {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
  // 将 key 转换成 hash
  loseloseHashCode(key) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }
  // 将 key 转换成 hash
  hashCode(key) {
    return this.loseloseHashCode(key);
  }
  // 将键和值加入到散列表中
  put(key, value) {
    if (key != null && value != null) {
        const position = this.hashCode(key);
      if (this.table[position] == null) {
          this.table[position] = new LinkedList();
      }
      this.table[position].push(new ValuePair(key, value));
      return true;
    }
    return false;
  }
  // 从散列表总获取一个值
  get(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if (linkedList != null && !linkedList.isEmpty()) {
        let current = linkedList.head();
      while(current != null) {
          if (current.element.key === key) {
            return current.element.value;
        }
        current = current.next;
      }
    }
    return undefined;
  }
  // 从散列表中移除一个值
  remove(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if (linkedList != null && !linkedList.isEmpty()) {
        let current = linkedList.head();
      while(current != null) {
          if (current.element.key === key) {
            linkedList.remove(current.element);
          if (linkedList.isEmpty()) {
              // delete this.table[position]
            Reflect.deleteProperty(this.table, position);
          }
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }
  // 获取整个散列表对象
  getTable() {
    return this.table;
  }
  // 判断散列表是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 返回散列表中的元素个数
  size() {
    return Object.keys(this.table).length;
  }
  // 清空散列表
  clear() {
    this.table = {};
  }
  // 将散列表转换成字符串并将其返回
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString}, {${keys[i]} => ${this.table[keys[i]].toString()}}`
    }
    return objString;
  }
}

线性探查

线性探查，其处理冲突的方法是将元素直接存储到散列表中，而不是在单独的数据结构中。

线性探查的原理

在一个已经包含一些元素的散列表中，我们想要添加一个新的键和值。我们计算这个新键的 hash，并检查散列表中对应的位置是否被占据，如果没有，我们就将该值添加到正确的位置，如果被占据了，我们就迭代散列表，直到找到一个空闲的位置，将元素添加到这个空闲的位置。

例如我们想在散列表中索引为 position 的位置添加一个新元素，但是当前位置已经被占据，就尝试 position + 1 的位置，如果 position + 1 的位置也被占据了，就尝试 position + 2 的位置，以此类推，直到在散列表中找到一个空闲的位置。

线性探查的实现

线性探查的实现由两种方式，一种是软删除，另一种是挪动位置。

挪动位置

这种方式需要检验是否有必要将一个或多个元素移动到之前的位置。当搜索一个键的时候，这种方法可以避免找到一个空位置。如果移动元素是必要的，我们就需要在散列表中挪动健值对。

使用挪动位置的方式实现线性探查，我们只需要重写 put、get、remove 三个方法即可，其余方法与 HashTable 类一致。

创建 HashTableLinearProbing 类

class HashTableLinearProbing {
    constructor(toStrFn = defaultToString) {
      this.toStrFn = toStrFn;
    this.table = {};
  }
}

put 方法

put(key, value) {
    if (key != null && value != null) {
    // 根据 key 生成在散列表中的位置
      const position = this.hashCode(key);
    // position 位置没有元素存在，则在该位置添加新元素
    if (this.table[position] == null) {
        this.table[position] = new ValuePair(key, value);
    } else {
      // 该 position 位置已经被占用，寻找下一个没有被占用的位置
        let index = position + 1;
      while(this.table[index] != null) {
          index++;
      }
      // 找到一个没有被占据的位置，在该位置上添加新元素
      this.table[index] = new ValuePair(key, value);
    }
    // 返回 true 表示元素成功添加到散列表中
    return true;
  }
  // 返回 false 表示元素没有添加到散列表中
  return false;
}

在 put 方法中，我们首先根据 key 生成一个位置，然后验证散列表中这个位置是否有元素存在，如果没有元素存在，就在该位置添加新元素。

如果该位置已经被占据了，就找下一个没有被占据的位置，因此我们声明一个 index 变量并赋值为 position + 1。然后验证该位置是否被占据，如果也被占据了，就继续将 index 递增，直到找到一个没有被占据的位置，然后将元素添加到该位置上。

get 方法

get(key) {
  // 根据 key 生成 hash 值，即在散列表中的位置
    const position = this.hashCode(key);
  // 散列表中 position 位置上有值
  if (this.table[position] != null) {
    // position 位置上的值恰好是我们要找的值，则返回这个值
      if (this.table[position].key === key) {
        return this.table[position].value;
    }
    // 不是我们要找的元素，继续在下一个位置查找
    let index = position + 1;
    // 按位置递增的顺序查找散列表上的元素直到找到我们要找的元素，或者找到一个空位置后，退出循环
    while(this.table[index] != null && this.table[index].key !== key) {
        index++;
    }
    // 退出循环后，验证元素的键是否是我们要找的键，如果是，则返回它的值
    if (this.table[index] != null && this.table[index].key === key) {
        return this.table[position].value
    }
  }
  // 如果迭代完整个散列表并且 index 上的位置是 undefined 或 null，说明要找的键不存在，返回 undefined
  // 要查找的的值不在散列表中，返回 undefined
  return undefined;
}

在 get 方法中，我们首先根据 key 生成 hash 值来检查整个位置上是否有值，如果该位置上是 undefined 或 null，说明要查找的值不在散列表中，因此可以返回 undefined。如果在该位置上有值，就要检查我们要找的值是否就是原始位置上的值，如果是，就返回这个值。

如果该位置上的值不是我们要找的值，则继续在下一个位置查找。我们会按照位置递增的顺序查找散列表上的元素直到找到我们要找的元素，或者找到一个空位置，此时跳出 while 循环。

当退出 while 循环的时候，我们要验证元素的键是否是我们要找的键，如果是，就返回该键对应的值。如果迭代完整个散列表并且 index 的位置上是 undefined 或 null 的话，说明要找的键不存在，我们就返回 undefined。

remove 方法

remove(key) {
    const position = this.hashCode(key);
  if (this.table[position] != null) {
    // 在 position 位置上找到要删除的元素，将该元素从散列表中删除
      if (this.table[position].key === key) {
        delete this.table[position];
      // 验证删除操作是否有副作用，如果有，需要将冲突的元素移动至一个之前的位置
      this.verifyRemoveSideEffect(key, position);
      return true;
    }
    // 在 position 位置上没有找到要删除的元素，迭代链表，直到找到要删除的元素
    let index = position + 1;
    while(this.table[index] != null && this.table[index].key !== key) {
        index++;
    }
    if (this.table[index] != null && this.table[index].key === key) {
        delete this.table[index];
      this.verifyRemoveSideEffect(key, position);
      return true;
    }
  }
  return false;
}

verifyRemoveSideEffect 方法

verifyRemoveSideEffect(key, removedPosition) {
  const hash = this.hashCode(key);
  let index = removedPosition + 1;
  while (this.table[index] != null) {
    const posHash = this.hashCode(this.table[index].key);
    if (posHash <= hash || posHash <= removedPosition) {
      this.table[removedPosition] = this.table[index];
      delete this.table[index];
      removedPosition = index;
    }
    index++;
  }
}

完整代码

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    const key = typeof this.key === 'object' ? JSON.stringify(this.key) : this.key;
    return `[#${key}: ${this.value}]`;
  }
}
const defaultToString = (item) => {
  if (item === null) {
    return 'NULL';
  } else if (item === 'undefined') {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  } else if (typeof item === 'object') {
    return JSON.stringify(item);
  }
  return item.toString();
}
class HashTableLinearProbing {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
  // 将 key 转换成 hash
  loseloseHashCode(key) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }
  // 将 key 转换成 hash
  hashCode(key) {
    return this.loseloseHashCode(key);
  }
  // 将键和值加入到散列表中
  put(key, value) {
    if (key != null && value !=null) {
        const position = this.hashCode(key);
      if (this.table[position] == null) {
          this.table[position] = new ValuePair(key, value); 
      } else {
          let index = position + 1;
        while(this.table[index] != null) {
            index++;
        }
        this.table[index] = new ValuePair(key, value);
      }
      return true;
    }
    return false;
  }
  // 从散列表总获取一个值
  get(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
        if (this.table[position].key === key) {
          return this.table[position].value;
      }
      let index = position + 1;
      while(this.table[index] != null && this.table[index].key !== key) {
          index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
          return this.table[position].value;
      }
    }
    return undefined;
  }
  // 从散列表中移除一个值
  remove(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
      if (this.table[position].key === key) {
            delete this.table[position];
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
      let index = position + 1;
      while(this.table[index] != null && this.table[index].key !== key) {
          index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
          delete this.table[index];
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
    }
    return false;
  }
  verifyRemoveSideEffect(key, removedPosition) {
    const hash = this.hashCode(key);
    let index = removedPosition + 1;
    while (this.table[index] != null) {
      const posHash = this.hashCode(this.table[index].key);
      if (posHash <= hash || posHash <= removedPosition) {
        this.table[removedPosition] = this.table[index];
        delete this.table[index];
        removedPosition = index;
      }
      index++;
    }
  }
  // 获取整个散列表对象
  getTable() {
    return this.table;
  }
  // 判断散列表是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 返回散列表中的元素个数
  size() {
    return Object.keys(this.table).length;
  }
  // 清空散列表
  clear() {
    this.table = {};
  }
  // 将散列表转换成字符串并将其返回
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString}, {${keys[i]} => ${this.table[keys[i]].toString()}}`
    }
    return objString;
  }
}

软删除

使用软删除的方式实现线性探查，我们需要使用一个特殊的值（标记）来表示健值对被删除了（惰性删除或软删除），而不是真的删除它。经过一段时间，散列表被操作过后，我们会得到一个标记了若干删除位置的散列表。

数据结构与算法学习之散列表

散列表

散列函数

MD5

SHA-1

实现散列表

定义 ValuePair 类

定义 defaultToString 函数

定义 HashTable 类

loseloseHashCode 将 key 生成散列值

hashCode 将 key 生成散列值

put 将键和值加入散列表

remove 从散列表中移除一个值

get 从散列表中获取一个值

getTable 获取整个散列表对象

isEmpty 判断散列表是否为空

size 返回散列表中的健值数量

clear 清空散列表

toString 将散列表转换成字符串并返回

完整代码

散列表中的冲突

分离链接

创建 HashTableSeparateChaining 类

put 将键和值加入散列表

get 从散列表中获取一个值

remove 从散列表中移除一个值

完整代码

线性探查

线性探查的原理

线性探查的实现

挪动位置

软删除