hanyeah

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

散列的两个重点问题：散列函数、处理冲突。

function hashInsert(t, x){
	var hk = h(x.key);
	t[hk] = x;
}

function hashSearch(t, k){
	var hk = h(k);
	return t[hk];
}

function hashDelete(t, x){
	var hk = h(x.key);
	t[hk] = null;
}

function chainHashInsert(t, x){
	var hk = h(x.key);
	t[hk] = t[hk] || [];
	t[hk].push(x);
}

function chainHashSearch(t, k){
	var hk = h(k);
	var a = t[hk];
	for(var i = 0; i < a.length;i++){
		if(a[i].key == k){
			return a[i];
		}
	}
	return null;
}

function chainHashDelete(t, x){
	var hk = h(k);
	var a = t[hk];
	for(var i = 0; i < a.length;i++){
		if(a[i].key == k){
			a.splice(i, 1);
			break;
		}
	}
}

var t = new Array(100);
for(var i = 0; i < 10; i ++){
	var x = {key: Math.random()};
	chainHashInsert(t, x);
	console.log("插入：",x);
}
console.log(t);

function h(k){
	return Math.floor(k*1000) % 100;
}

/*function h(k){
	return Math.floor(100*(k*618%1));
}*/

/*function h(k){
	return Math.floor(k*100);
}*/

https://github.com/hanyeah/lianxi/tree/master/算法导论/10