algorithm
散列算法的作用是盡可能快地在數(shù)據(jù)結(jié)構(gòu)中找到一個值苍凛。通常在集合中獲取一個值的做法都是遍歷整個數(shù)據(jù)結(jié)構(gòu)來找到想要的值箍铭。如果用散列函數(shù)螟炫，就知道值的具體位置赁豆，所以很快就能檢索到想要的值仅醇。
hashTable 是經(jīng)常在 java 面試被問到的知識點，所以想要面試 java 開發(fā)可以準備一下看一下 hashTable 和 hashSet 的相關(guān)知識點魔种。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>散列表(Hash Table)</title>
<link rel="stylesheet" href="index.css">
<link rel="stylesheet"
integrity="sha384-nn4HPE8lTHyVtfCBi5yW9d20FjT8BJwUXyWZT9InLYax14RDjBj46LmSztkmNP9w" crossorigin="anonymous">
</head>
<body>
<div class="wrapper">
<table id="hashTable" class="pure-table">
<thead>
<tr>
<td>名稱</td>
<td>散列函數(shù)</td>
<td>散列值</td>
<td>散列表</td>
</tr>
</thead>
<tbody>
<tr>
<td></td>
</tr>
</tbody>
</table>
</div>
<script src="demo.js"></script>
</body>
</html>
為了可視化 hash 表我做了一個 index.html 很簡單析二，最近也懶得寫 css 直接引用 pure.css 然后將我們生成散列表打印出來。
這方法很簡單但是很有效地將一個值的字母ASCII值相加作為查詢碼节预。
const tableEle = document.querySelector("#hashTable");
/**
* 先創(chuàng)建
* {key:string,hash:string,hashVal:number,value:string}
*/
function createRow(obj){
let rowElement = document.createElement("tr");
let keyTrElement = document.createElement("td");
keyTrElement.innerText=obj.key;
let hashTrElement = document.createElement("td");
hashTrElement.innerText = obj.hash;
let hashValTrElement = document.createElement("td");
hashValTrElement.innerText = obj.hashVal;
let valueTrElement = document.createElement("td");
valueTrElement.innerText = obj.value;
rowElement.appendChild(keyTrElement);
rowElement.appendChild(hashTrElement);
rowElement.appendChild(hashValTrElement);
rowElement.appendChild(valueTrElement);
tableEle.appendChild(rowElement);
return rowElement;
}
function HashTable(){
var table = [];
this.put = function(key,value){
var position = loseloseHashCode(key);
console.log(position + ' - ' + key);
table[position] = value;
const obj = {
key:key,
hash:'',
hashVal:position,
value:value
}
createRow(obj);
}
this.get = function(key){
return table[loseloseHashCode(key)]
}
this.remove = function(key){
table[loseloseHashCode(key)] = undefined;
}
var loseloseHashCode = function(key){
var hash = 0;
for(var i = 0; i < key.length; i++){
hash += key.charCodeAt(i);
}
return hash % 37;
}
}
var tutHashTable = new HashTable();
tutHashTable.put('angular','javascript');
tutHashTable.put('spring','java');
tutHashTable.put('flask','python');
function showHashCode(key){
var hash = 0;
for(var i = 0; i < key.length; i++){
hash += key.charCodeAt(i) + " - ";
}
console.log(key + " -> " + hash);
return hash % 35;
}
showHashCode('angular');
showHashCode('spring');
showHashCode('flask');
圖1
有時候叶摄，一些鍵會有相同的散列值。我們稱這種情況為沖突安拟。
tutHashTable.put('angular','javascript');
tutHashTable.put('spring','java');
tutHashTable.put('flask','python');
tutHashTable.put('react','reactjs')
tutHashTable.put('vue','vuejs')
tutHashTable.put('babylon','babylonjs')
tutHashTable.put('three','threejs')
tutHashTable.put('underscore','underscorejs')
tutHashTable.put('react-spring','reactspring');
tutHashTable.put('jquery','jqueryjs');
tutHashTable.put('call','string-query');
創(chuàng)建一個遍歷 hashTable 方法
圖2
this.print = function(){
for(let i = 0; i < table.length; ++i){
if(table[i] !== undefined){
console.log(i + ": " + table[i]);
}
}
}
發(fā)現(xiàn) underscorejs 覆蓋掉了 reactjs 蛤吓，所有因為可能有相同hash值，也就是 hash 值沖突前面的值被后來值覆蓋掉了糠赦。我們怎么來解決這樣的問題呢会傲？
圖3
有幾種方法可以解決上面的問題: 分離鏈接、線性探查和雙散列法可以解決
分離鏈接
是為散列表的每一個位置創(chuàng)建一個鏈表并將元素保存在鏈表里面拙泽。
var ValuePair = function(key, value){
this.key = key;
this.value = value;
this.toString = function(){
return `[ ${this.key} - ${this.value} ]`
}
}
我們引入 LinkedList
<script src="linkedList.js"></script>
<script src="demo.js"></script>
this.put = function(key,value){
var position = loseloseHashCode(key);
if(table[position] == undefined){
table[position] = new LinkedList();
}
table[position].append(new ValuePair(key,value));
const obj = {
key:key,
hash:'',
hashVal:position,
value:value
}
createRow(obj);
}
this.get = function(key){
let position = loseloseHashCode(key);
if(table[position] !== undefined){
let current = table[position].getHead();
while(current.next){
if(current.element.key === key){
return current.element.value;
}
current = current.next;
}
if(current.element.key === key){
return current.element.value;
}
}
return undefined;
}
- 首先hash所對應(yīng)的鏈表是否存在淌山，如果不存在直接返回 undefined。
this.remove = function(key){
let position = loseloseHashCode(key);
if(table[position] !== undefined){
let current = table[position].getHead();
while(current.next){
if(current.element.key === key){
table[position].remove(current.element);
if(table[position].isEmpty()){
table[position] = undefined;
}
return true;
}
current = current.next;
}
if(current.element.key === key){
table[position].remove(current.element);
if(table[position].isEmpty()){
table[position] = undefined;
}
return true;
}
}
return false;
}
圖5
javascript
線性探索
另一種解決沖突的方法就是線性探索顾瞻。當(dāng)想要向表中某個位置加入一個新元素的時候艾岂，如果索引為 index 的位置已經(jīng)被占用，就向后順延 1 位保存數(shù)據(jù)
