数据结构(四)-实现字典对象和散列表(hashMap)、Map类实现字典和散列表

上一节讲了集合，虽然集合和散列表也是类似集合的键值对，但是集合我们只关注值，形式是 [值，值]。在字典和散列表当中，通过[键，值]的形式来存储数据,又称之为关联数组，这也就是可以通过[]来访问对象的原因

字典

// 因为字典的key有可能不是字符串，所以需要，将字典的key转换为字符串
  function defaultToString (item) {
    if (item === null) {
      return `NULL`
    } else if (item === 'undefined') {
      return `UNDEFINED`
    } else if (typeof item === 'string' || item instanceof String) {
      return `${item}`
    }
    return item.toString()
  }

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

set(key,value)方法添加新元素

set(key,value) {
  if (key !== null && value !== null) {
    // value是一个ValuePair类，同时保存了当前的key以及value
    this.table[this.toStrFn(key)] = new ValuePair(key,value)// name : {key:name,value:'Rick'}
    return true
  }
  return false
}

hasKey(key)键值是否存在于

hasKey (key) {
      return !!this.table[this.toStrFn(key)]
    }

remove(key)方法删除元素

removeKey (key) {
  if (this.hasKey[key]) {
    delete this.table[this.toStrFn(key)]
    return true
  }
  return false
}

get(key)查找特定的值

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

clear()删除所有值

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

isEmpty()是否为空

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

keys()获取字典中所有的key数组

keys() {
  return this.keyValues().map(valuePair => v.key)
}

values()获取字典中所有value数组

values() {
  return this.keyValues().map(valuePair => v.value)
}

keyValues()返回所有[键，值]

keyValues() {
  return Object.values(this.table)
}

forEach(callbackFn)迭代字典中所有的键值对

// 和forEach方法一样，接收一个callback，由用户传递
forEach(callback) {
  // 获取所有的value
  const values = this.keyValues()
  // 遍历value
  for (let i = 0; i < values.length; i++) {
    // 执行用户传入的回调函数
    const result = callback(values[i].key,values[i].value)
    // 如果用户传入的执行结果返回了false，那么中断当前的操作
    if (result == false) {
      break
    }
  }
}

散列表(hashMap)

hashTable类，也叫hashMap类,是字典类的一种散列实现方式
比如在下面的图中，Gandalf名称key是5个字符，将这5个字符计算出ASCII值相加，就是散列值

创建散列表

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

创建散列函数

散列函数的作用就是将字符串的key的ASCII值相加,计算出一个散列值

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) // 获取当前key的每一个字符串ASCII码总和
  }
  return hash % 37 // 模运算防止数值超过最大范围风险，37是随机的
}
hashCode (key) {
  return this.loseloseHashCode(key)
}

实现put增加/更新方法

// 给hashMap设置值，也可以称作set
   put (key, value) {
     if (key !== null && value !== null) {
        const position = this.hashCode(key)
        this.table[position] = new ValuePair(key,value)
        return true
     }
     return false
   }

实现remove(key)移除方法

remove (key) {
      const hash = this.hashCode(key)
      const valuePair = this.table[hash]
      if (valuePair) {
        delete this.table[hash]
        return true
      }
      return false
    }

实现get(key)方法

 get(key) {
      const valuePair = this.table[this.hashCode(key)]
      return valuePair == null ? undefined : valuePair.value
    }
const hash = new HashTable()
hash.put("John",'johnsnow@email.com')
hash.put("Gandalf",'gandalf@email.com')
console.log(hash.get("Gandalf")) // gandalf@email.com

测试HashTable类

/**
   * {
   *  19:{
   *    key:"Gandalf",
   *    value:"gandalf@email.com"
   *   }
   * 29: {
   *    key: "John"
        value: "johnsnow@email.com"
   *  }
   * }
   * 
   * 
   **/
  const hash = new HashTable()
  hash.put("John",'johnsnow@email.com')
  hash.put("Gandalf",'gandalf@email.com')

  console.log(hash.hashCode('John')) // 29
  console.log(hash.hashCode('Gandalf')) // 19
  console.log(hash)
  console.log(hash.get("Gandalf")) // gandalf@email.com

处理散列表冲突

只把字符串转为ASCII值相加起来的话，，一些键可能会有相同的散列值，可能会有hash冲突，导致key相同被覆盖，解决方法一般有分离链接,线性探查，双散列法

{
    19:{
        element:{
            value:"Jonathan",
            key:"jonathan@email.com"
        },
        next:{
            element:{
                value:"Jamie",
                key:"Jamie@email.com"
            },
            next:{
                element:{
                    value:"Sue",
                    key:"Sue@email.com"
                },
                next:...
            }
        }
    }
}

分离链接修改put方法

put(key,value) {
      if (key !== null && value !== null) {
        const position = this.hashCode(key)
        // 如果这个hash不存在
        if (!this.table[position]) {
          // 初始化为一个空链表
          this.table[position] = new LinkedList()
        }
        // 给这个链表添加一个值为new ValuePair(key,value)类
        this.table[position].push(new ValuePair(key,value))
        return true
      }
      return false
    }

分离链接修改get方法

get(key) {
      const linkedList = this.table[this.hashCode(key)]
      if (linkedList && !linkedList.isEmpty()) {
        let current = linkedList.getHead()
        while(current) {
          if (current.element.key === key) {
            return current.element.value

          }
          current = current.next
        }
      }
      return undefined
    }

分离链接修改remove方法

removep; (key) {
      const linkedList = this.table[this.hashCode(key)]
      if (linkedList && !linkedList.isEmpty()) {
        let current = linkedList.getHead()
        while(current) {
          if (current.element.key === key) {
            linkedList.remove(current.element)
            if (linkedList.isEmpty()) {
              // 如果删除之后已经空了，清除掉这个hash
              delete this.table[position]
            }
            return true
          }
          current = current.next
        }
      }
      return false
    }

ES6的Map类

Map类的底层实现就是hashMap，也就是上面的hash+链表

Map和Object的区别

• Map是有顺序的，频繁增删性能更好,key可以是任意值,
• Object是无序的，没有对频繁增删进行优化，key是字符串

WeakMap类和WeakSet类

键值必须是对象，键值是弱引用