数据结构—散列表
2019-05-31 本文已影响13人
zidea
algorithm
散列算法的作用是尽可能快地在数据结构中找到一个值。通常在集合中获取一个值的做法都是遍历整个数据结构来找到想要的值。如果用散列函数，就知道值的具体位置，所以很快就能检索到想要的值。
hashTable 是经常在 java 面试被问到的知识点，所以想要面试 java 开发可以准备一下看一下 hashTable 和 hashSet 的相关知识点。
<!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" href="https://unpkg.com/purecss@1.0.0/build/pure-min.css"
integrity="sha384-nn4HPE8lTHyVtfCBi5yW9d20FjT8BJwUXyWZT9InLYax14RDjBj46LmSztkmNP9w" crossorigin="anonymous">
</head>
<body>
<div class="wrapper">
<table id="hashTable" class="pure-table">
<thead>
<tr>
<td>名称</td>
<td>散列函数</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");
/**
* 先创建
* {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');
创建一个遍历 hashTable 方法
图2
this.print = function(){
for(let i = 0; i < table.length; ++i){
if(table[i] !== undefined){
console.log(i + ": " + table[i]);
}
}
}
发现 underscorejs 覆盖掉了 reactjs ，所有因为可能有相同hash值，也就是 hash 值冲突前面的值被后来值覆盖掉了。我们怎么来解决这样的问题呢？
图3
有几种方法可以解决上面的问题: 分离链接、线性探查和双散列法可以解决
分离链接
是为散列表的每一个位置创建一个链表并将元素保存在链表里面。
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所对应的链表是否存在，如果不存在直接返回 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
线性探索
另一种解决冲突的方法就是线性探索。当想要向表中某个位置加入一个新元素的时候，如果索引为 index 的位置已经被占用，就向后顺延 1 位保存数据
