1、HashCode实现

  1. // 散列函数实现, 长度11的素数为例
  2. const handleHashCode = (key = "") => {
  3.     let hashCode = 0;
  4.     for(let i=0; i<key.length; i++) {
  5.         // 注: charCodeAt() 方法可返回指定位置的字符的 Unicode 编码
  6.         hashCode += key.charCodeAt(i)
  7.     }
  8.     // console.log("hashCode: ", hashCode % 11)
  9.     // 素数: 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061
  10.     return hashCode % 11
  11. }

2、开放定址法实现hashMap

  1. const { handleHashCode } = require('./hashCode')
  3. // put进去的object = {key: value}
  4. class putValue {
  5.     constructor(key, value) {
  6.         this.key = key
  7.         this.value = value
  8.     }
  9. }
  11. // 实现hashMapLine
  12. class HashMapLine {
  13.     constructor() {
  14.         this.map = []
  15.     }
  17.     // put元素
  18.     put(key, value) {
  19.         // 1、获取位置
  20.         let position = handleHashCode(key)
  21.         // 2、position位置上的值不为undefined、null
  22.         while(this.map[position] !== undefined && this.map[position] !== null) {
  23.             position += 1
  24.         }
  25.         // 3、插入值
  26.         this.map[position] = new putValue(key, value)
  27.     }
  29.     // get元素
  30.     get(key) {
  31.         let position = handleHashCode(key)
  32.         // 1、判断position位置的元素是否存在
  33.         while(this.map[position] !== undefined) {
  34.             // 2、判断position位置的key相等就返回value, 否则+1
  35.             if(this.map[position] !== null &&  this.map[position].key === key) {
  36.                 return this.map[position].value
  37.             }
  38.             position += 1
  39.         }
  40.         return false
  41.     }
  43.     // remove元素
  44.     remove(key) {
  45.         let position = handleHashCode(key)
  46.         // 1、判断position位置的元素是否存在
  47.         while(this.map[position] !== undefined) {
  48.             // 2、判断position位置的key相等就将postion置位null, 否则+1
  49.             if(this.map[position] !== null && this.map[position].key === key) {
  50.                 this.map[position] = null
  51.                 return true
  52.             }
  53.             position += 1
  54.         }
  55.         return false
  56.     }
  58.     getItems() {
  59.         return this.map
  60.     }
  61. }
  64. // 测试 case
  65. const hashmap = new HashMapLine()
  66. hashmap.put("Donnie", "1111@qq.com")
  67. hashmap.put("ab", "2222@qq.com")
  68. hashmap.put("Ana", "3333@qq.com")
  69. console.log("hashCode: ", handleHashCode("ab"))
  70. console.log("hashCode: ", handleHashCode("Ana"))
  71. console.log(hashmap.getItems())
  73. hashmap.remove("Donnie")
  74. hashmap.remove("Ana")
  75. console.log(hashmap.getItems())
  76. hashmap.put("Ana", "4444@qq.com")
  77. console.log(hashmap.getItems())

3、拉链法实现hashMap

  1. const { handleHashCode } = require('./hashCode')
  2. const { SingleLinkedList } = require('./LinkedList')
  4. // put进去的object = {key: value}
  5. class putValue {
  6.     constructor(key, value) {
  7.         this.key = key
  8.         this.value = value
  9.     }
  10. }
  12. class HashMapLinked {
  13.     constructor() {
  14.         this.map = []
  15.     }
  17.     // put<K, V>
  18.     put(key, value) {
  19.         let position = handleHashCode(key)
  20.         if(this.map[position] === undefined) {
  21.             // 第一次插入, 初始化链表
  22.             this.map[position] = new SingleLinkedList()
  23.         }
  24.         this.map[position].append(new putValue(key, value))
  25.     }
  27.     // get<K>
  28.     get(key) {
  29.         let position = handleHashCode(key)
  30.         // 判断当前位置是否存在元素
  31.         if(this.map[position] === undefined) {
  32.             return false
  33.         }else {
  34.             let currentNode = this.map[position].head
  35.             // 找到node节点
  36.             while(currentNode) {
  37.                 if(currentNode.val.key === key) {
  38.                     return currentNode.val.value
  39.                 }
  40.                 currentNode = currentNode.next
  41.             }
  42.             return false
  43.         }
  44.     }
  46.     // remove<K>
  47.     remove(key) {
  48.         let position = handleHashCode(key)
  49.         if(this.map[position] === undefined) {
  50.             return false
  51.         }else {
  52.             let currentNode = this.map[position].head
  53.             let index = 0
  54.             while(currentNode) {
  55.                 // 删除链表对应的位置
  56.                 if(currentNode.val.key === key) {
  57.                     // console.log(this.map[position])
  58.                     this.map[position].remove(index)
  59.                 }
  60.                 // 空链表进行初始化
  61.                 if(this.map[position].isEmpty()) {
  62.                     this.map[position] = undefined
  63.                 }
  64.                 currentNode = currentNode.next
  65.                 index += 1
  66.             }
  67.             return false
  68.         }
  69.     }
  71.     getItems() {
  72.         return this.map
  73.     }
  74. }
  76. // 测试 case
  77. const hashmap = new HashMapLinked()
  78. hashmap.put("Donnie", "1111@qq.com")
  79. hashmap.put("ab", "2222@qq.com")
  80. hashmap.put("Ana", "3333@qq.com")
  81. console.log("hashCode: ", handleHashCode("ab"))
  82. console.log("hashCode: ", handleHashCode("Ana"))
  83. console.log(hashmap.getItems())
  85. hashmap.remove("Donnie")
  86. hashmap.remove("Ana")
  87. console.log(hashmap.getItems())
  88. hashmap.put("Ana", "4444@qq.com")
  89. console.log(hashmap.getItems())