概念和用途

  • 散列后的数据可以快速插入取用
  • 在散列表上插入、删除和取用数据非常快，但是查找数据却效率低下，比如查找一组数据中的最大值和最小值
  • ◆JavaScript散列表基于数组设计，理想情况散列函数会将每一个键值映射为唯的数组索引，数组长度有限制，更现实的策略是将键均匀分布。

关键定义

  • 两个键值相同的情况，这种现象称为碰撞
  • 数组长度应该是一个质数，所有策略都基于碰撞
  • 开链法：两个键相同保存位置一样，开辟第二数组，也称第二个数组为链
  • 线性探测法属于开放寻址散列，查找散列位置如果当前位置没有继续寻找下一个位置。
  • 存储数据较大较合适。数组大小》=1.5数据，使用开链法，数组大小》=2数据，使用线性探测法。

代码实现

  1. function hashTable() {
  2.     // 1. 给质数长度的数组，为了防碰撞
  3.     this.table = new Array(159)
  4.     // 2.1 获取hash
  5.     this.simpleHash = simpleHash
  6.     // 2.2 展示hash
  7.     this.display = display
  8.     // 2.3 增
  9.     this.put = put
  10.     // 2.4 查
  11.     this.get = get
  12.     // 3.1 解决碰撞1：betterHash
  13.     this.betterHash = betterHash
  14.     // 3.2 解决碰撞2：开链法——创造一个数组，存在了就push进去
  15.     this.buildChain = buildChain
  16.     // 3.3 解决碰撞3：线性探测法——如果碰撞了，则一直往下找到没有碰撞的位置（如果找到最后都没有位置呢？插入失败？）
  17. }
  18. function buildChain () {
  19.     for (let index = 0; index < this.table.length; index++) {
  20.         this.table[index] = []
  21.     }
  22. }
  23. function simpleHash(ele) {
  24.     var total = 0;
  25.     for (let index = 0; index < ele.length; index++) {
  26.         // string.charCodeAt(i)    string.charAt(i)
  27.         // 'abc'.charCodeAt(1) == 98    'abc'.charAt(1) == b   
  28.         total += ele.charCodeAt(index)
  29.     }
  30.     // 就这么记吧，我也不知道为啥，哎
  31.     // console.log('simpleHash res is :', total % 137)
  32.     return total % 137
  33. }
  35. function betterHash(ele) {
  36.     // 放大算法，在total上乘上个质数  让结果更均匀一些
  37.     const GG = 99
  38.     var total = 0;
  39.     for (let index = 0; index < ele.length; index++) {
  40.         total += total * GG + ele.charCodeAt(index)
  41.     }
  42.     console.log('simpleHash res is :', total % 137)
  43.     return total % 137
  44. }
  46. function display() {
  47.     for (let index = 0; index < this.table.length; index++) {
  48.         if (this.table[index]) {
  49.             console.log(`index: ${index}, value: ${this.table[index]}`)
  50.         }
  51.         // 开链法改造:
  52.         // if (this.table[index][0]) {
  53.         //     console.log(`index: ${index}, value: ${this.table[index]}`)
  54.         // }
  55.     }
  57. }
  59. function put(ele) {
  60.     var pos = this.simpleHash(ele)
  61.     // this.table[pos] = ele
  62.     // 线性探测法判断空位
  63.     if (!this.table[pos]) { 
  64.         this.table[pos] = ele
  65.     } else {
  66.         while(this.table[pos] != undefined) {
  67.             pos++
  68.         }
  69.         this.table[pos] = ele
  70.     }
  71.     // 开链法改造：
  72.     // var index = 0
  73.     // if (!this.table[pos][index]) {
  74.     //     this.table[pos][index] = ele
  75.     // } else {
  76.     //     while(this.table[pos][index] != undefined) {
  77.     //         index++
  78.     //     }
  79.     //     this.table[pos][index] = ele
  80.     // }
  81. }
  82. function get(ele) {
  83.     // 第一次实现是下面这个东西，看起来很蠢
  84.     // return this.table[key]
  85.     // 课程实现的是下面这东西，看起来很厉害的蠢
  86.     // return this.table[this.simpleHash(ele)]
  88.     // 线性探测法，来获取原本的index和最终的index
  89.     var hash = this.simpleHash(ele)
  90.     // 从hash开始是因为碰撞是从 hash开始的
  91.     console.log('原始hash： ', hash)
  92.     for (let index = hash; index < this.table.length; index++) {
  93.         if (this.table[index] == ele) {
  94.             return index
  95.         }
  96.     }
  97.     return false
  98. }
  100. var hashT = new hashTable()
  101. // hashT.buildChain()
  102. hashT.put('china')
  103. hashT.put('japan')
  104. hashT.put('america')
  105. // 与china产生了碰撞，接下来改进hash算法
  106. hashT.put('incha')
  107. hashT.put('incha')
  108. hashT.put('incha')
  109. hashT.put('incha')
  110. hashT.put('incha')
  111. hashT.put('incha')
  112. hashT.put('incha')
  113. hashT.put('incha')
  114. hashT.put('incha')
  115. hashT.put('incha')
  116. hashT.put('incha')
  117. hashT.put('incha')
  118. hashT.put('incha')
  119. hashT.put('incha')
  120. hashT.put('incha')
  121. hashT.put('incha')
  122. hashT.put('incha')
  123. hashT.put('incha')
  124. hashT.put('incha')
  125. hashT.put('incha')
  126. hashT.put('incha')
  127. hashT.put('incha')
  128. hashT.put('incha')
  129. hashT.put('incha')
  130. hashT.put('incha')
  131. hashT.put('incha')
  132. hashT.put('incha')
  133. hashT.put('incha')
  134. hashT.put('incha')
  135. hashT.put('incha')
  136. hashT.put('incha')
  137. hashT.put('incha')
  138. hashT.put('incha')
  139. hashT.put('incha')
  140. hashT.put('incha')
  141. hashT.put('incha')
  142. hashT.put('incha')
  143. hashT.put('incha')
  144. hashT.put('incha')
  145. hashT.put('incha')
  146. hashT.put('incha')
  147. hashT.put('incha')
  148. hashT.put('incha')
  149. hashT.put('incha')
  150. hashT.put('incha')
  151. hashT.put('incha')
  152. hashT.put('incha')
  153. hashT.put('incha')
  154. hashT.put('incha')
  155. hashT.put('incha')
  156. hashT.put('incha')
  157. hashT.put('incha')
  158. hashT.put('incha')
  159. hashT.put('incha')
  160. hashT.put('incha')
  161. hashT.put('incha')
  162. hashT.put('incha')
  163. hashT.put('incha')
  164. hashT.put('incha')
  165. hashT.put('incha')
  166. hashT.put('incha')
  167. hashT.put('incha')
  168. hashT.put('incha')
  169. hashT.put('incha')
  170. hashT.put('incha')
  171. hashT.put('incha')
  172. hashT.put('incha')
  173. hashT.put('incha')
  174. hashT.put('incha')
  175. hashT.put('incha')
  176. hashT.put('incha')
  177. hashT.put('incha')
  178. hashT.put('incha')
  179. hashT.put('incha')
  180. hashT.put('incha')
  181. hashT.put('incha')
  182. hashT.put('incha')
  183. hashT.put('incha')
  184. hashT.put('incha')
  185. hashT.put('incha')
  186. hashT.put('incha')
  187. hashT.put('incha')
  188. hashT.put('incha')
  189. hashT.put('incha')
  190. hashT.put('incha')
  191. hashT.put('incha')
  192. hashT.put('incha')
  193. hashT.put('incha')
  194. hashT.put('incha')
  195. hashT.put('incha')
  196. hashT.put('incha')
  197. hashT.put('incha')
  198. hashT.put('incha')
  199. hashT.put('incha')
  200. hashT.put('incha')
  201. hashT.put('incha')
  202. hashT.put('incha')
  203. hashT.put('incha')
  204. hashT.put('incha')
  205. console.log('length:', hashT.table.length, '------------------------')
  206. // 所以就溢出了呗，这个后面有用到这玩意再说吧，先了解着
  207. hashT.display()
  208. console.warn(hashT.get('incha'))