数据结构--哈希表

[lznbuild]

哈希表

跟js中的对象有点类似，也是key-value的存储形式，不同点在于实际的键值和存入的值之间存在一层哈希值的映射

class HashTable {
  constructor(){
    this.items={}
  }

  get(key){
    // 把传入的key转换为哈希值，通过哈希值去找对应的值
    const hash = this.keyToHash(key);
    return this.items[hash]
  }

  set(key,value){
    const hash=this.keyToHash(key);
    this.items[hash] = value
  }

  remove(key){
    const hash = this.keyToHash(key);
    delete this.items[hash]
  }
  // 把key转换为hash
  keyToHash(key){
    //把字符串key，变成数字
    let hash=0;
    for(let i=0;i<key.length;i++){
      hash+=key[i].charCodeAt() // 获取key的ascll码
    }
    hash = hash%37 
    // 数字会在37以内
    return hash
  }
}

上面那个keyToHash，可能会转换出来重复的hash，比如'az','by'这种key就对应同一个hash，都是34，这就是哈希冲突问题。

哈希冲突问题

解决方案1：分离连接，给哈希表的每一项添加链表，重复项通过链表连接。

解决方案2：线性探查，在当前hash位置往后排。

// 方案1

     // 辅助类：节点
    class Node {
      constructor(element) {
        this.element = element;
        this.next = null
      }
    }

    class likedList {
      constructor() {
        // 链表头
        this.head = null;
        // 链表长度
        this.length = 0;
      }

      // 链表尾添加元素
      append(element) {
        var node = new Node(element);

        if (this.head == null) {
          // 只会在向链表添加第一次的时候执行
          this.head = node
          this.length++
        } else {
          var current = this.head;
          while (current.next) {
            current = current.next
          }

          //while执行完毕后，current.next 为null,current是链表的最后一项
          current.next = node;
          this.length++;
        }
      }

      //链表某一个位置添加元素
      insert(position, element) {
        //越界
        if (position > -1 && position < this.length) {
          var node = new Node(element);

          if (position == 0) {
            var current = this.head;
            this.head = node;
            this.head.next = current
            this.length++
          } else {
            var index = 0;
            var current = this.head;
            var previous = null;
            while (index < position) {
              previous = current;
              current = current.next;
              index++;
            }
            previous.next = node;
            node.next = current
          }

          this.length++
        }
      }

      // 删除某一个位置的元素
      removeAt(position) {
        if (position > -1 && position < this.length) {
          if (position == 0) {
            let current = this.head;
            this.head = this.head.next;
            return current.element
          } else {
            var current = this.head;
            var previous = null;
            var index = 0;
            while (index < position) {
              previous = current;
              current = current.next;
              index++;
            }

            // 出循环的时候，index == position
            previous.next = current.next
          }

          this.length--;
          return current.element //返回删除项
        }
        return null
      }

      //删除某一项
      remove(element) {
        return this.removeAt(this.indexOf(element))
      }

      // 查找
      indexOf(key) {
        var current = this.head;
        var index = 0;
        while (current) {
          if (current.element.key == key) {
            return index
          }
          index++;
          current = current.next
        }

        return -1
      }

      isEmpty() {
        return this.length == 0
      }

      size() {
        return this.length
      }

      getHead() {
        return this.head
      }
    }

   class Node2 {
      constructor(key, value) {
        this.key = key;
        this.value = value;
      }
    }

  // 链表和哈希表的结合
  class HashTable_L {
    constructor(){
      this.items = {}
    }

    keyToHash(key){
      //把字符串key，变成数字
      let hash = 0;
      for (let i = 0; i < key.length; i++) {
        hash += key[i].charCodeAt() // 获取key的ascll码
      }
      hash = hash % 37
      // 数字会在37以内
      return hash
    }

    set(key, value){
      const hash = this.keyToHash(key);
      if (this.items[hash]) {
        // 已经有值的情况下
        this.items[hash].append(new Node2(key, value))
      } else {
        // 没值的情况下
        const l = new likedList() // 链表
        this.items[hash] = l;
        this.items[hash].append(new Node2(key, value));
      }
    }

    get(key){
      // key 'az'
      const hash = this.keyToHash(key);
      if (this.items[hash]) {
        // 链表线性查找
        let current = this.items[hash].head;
        while(current.element){
          if(current.element.key == key){
            return current.element.value
          }
          current = current.next
        }
      }
      return null
    }

    remove(key){
      // key 'az'
      const hash = this.keyToHash(key);
      if (this.items[hash]) {
        // 删除

        return this.items[hash].remove(key)
      } else {
        return false
      }
    }
  }

  // az   by

  var like = new HashTable_L();
  like.set('az', 123);
  like.set('by', 456);
  like.set('yu', 789);

// 线性探查
  class Node {
    constructor(key, value) {
      this.key = key;
      this.value = value;
    }
  }

  class HashTable_X {
    constructor(){
      this.table = []
    }

    loseloseHashCode (key) {
      var hash = 0;
      for (var i = 0; i < key.length; i++) {
        hash += key[i].charCodeAt()
      }
      return hash % 37
    }

    put(key, value) {
      var position = this.loseloseHashCode(key);
      if (this.table[position] == undefined) {
        this.table[position] = new Node(key, value)
      } else {
        //这个位置被占了
        var index = position + 1;
        while (this.table[index] !==undefined) {
          index++
        }
        this.table[index] = new Node(key, value)
      }
    }

    get(key) {
      var position = this.loseloseHashCode(key);

      while(this.table[position].key !== key){
        position+=1;
      }

      return this.table[position].value
    }

    remove(key) {

    }
  }

  var list = new HashTable_X();
  list.put('az',123);
  list.put('by',456);
  list.put('cx',789);
  list.put('yu',9);

// loseloseHashCode的替换方法
var djb2HashCode = function(key){
  var hash = 5831;
  for(var i=0;i<key.length;i++){
    hash = hash*33+key[i].charCodeAt();
  }
  return hash%1013
}
//数学问题，不会有冲突