HashTable
(也叫HashMap
)的数据结构存储大家的信息hash
值,使用分离链接
或者线性探测
解决冲突泪奔
)hashTable
class HashTable {
constructor() {
this.table = []; // 数组形式存储
}
// 散列运算函数,可自定义
// 此处时最常见的散列函数 ‘lose lose’
static loseloseHashCode(key) {
let hash = 0;
for (var i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
//对hash取余,这是为了得到一个比较小的hash值,
//但是这里取余的对象又不能太大,要注意
return hash % 37;
}
// 修改和增加元素
put(key, value) {
const position = HashTable.loseloseHashCode(key);
console.log(`${position} - ${key}`);
this.table[position] = value;
}
get(key) {
return this.table[HashTable.loseloseHashCode(key)];
}
remove(key) {
this.table[HashTable.loseloseHashCode(key)] = undefined;
}
}
const hash = new HashTable();
hash.put('Surmon', 'surmon.me@email.com') // 15 - Surmon
hash.put('Jhon', 'Jhonsnow@email.com') // 29 - Jhon
hash.put('Tyrion', 'Tyrion@email.com') // 16 - Tyrion
console.log(hash.get('Surmon')); // surmon.me@email.com
console.log(hash.get('Loiane')); // undefined
console.log(hash)
JS
里面实现哈希表,用的是数组形式。通过key计算出hash作为下标,将value
作为下标对应在数组中的值。undefined
,但是如果key值计算后得到的hash
值重复了,那怎么办?会被覆盖掉。我们不允许出现这个问题.因为我们要把所有人的信息都存进去,今天介绍两种方法:
JS
数组可以动态拓展长度,这个问题不存在)简单来说:就是初次发现这个下标被存储占用了(说明重复了)就会把下标自增1,然后继续查找空的下标用于存储信息
用JS实现单链表
function LinkedList() {
// Node辅助类,表示要加入列表的项,element是即将添加到列表的值,next是指向列表中下一个节点项的指针
let Node = function (element) {
this.element = element
this.next = null
}
let length = 0
let head = null
// 向链表尾部追加元素
this.append = function (element) {
let node = new Node(element)
let current
if (head === null) { // 列表中第一个节点
head = node
} else {
current = head
while (current.next) {
current = current.next // 找到最后一项,是null
}
current.next = node // 给最后一项赋值
}
length++ // 更新列表的长度
}
// 从链表中移除指定位置元素
this.removeAt = function (position) {
if (position > -1 && position < length) { // 值没有越界
let current = head
let previous, index = 0
if (position === 0) { // 移除第一项
head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next // 将previous与current的下一项连接起来,跳过current,从而移除
}
length-- // 更新列表的长度
return current.element
} else {
return null
}
}
// 在链表任意位置插入一个元素
this.insert = function (position, element) {
if (position >= 0 && position <= length) { // 检查越界值
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) { // 在第一个位置添加
node.next = current
head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current // 在previous与current的下一项之间插入node
previous.next = node
}
length++
return true
} else {
return false
}
}
// 把链表内的值转换成一个字符串
this.toString = function () {
let current = head,
string = ''
while (current) {
string += current.element + ' '
current = current.next
}
return string
}
// 在链表中查找元素并返回索引值
this.indexOf = function (element) {
let current = head,
index = 0
while (current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
// 从链表中移除指定元素
this.remove = function (element) {
let index = this.indexOf(element)
return this.removeAt(index)
}
this.isEmpty = function () {
return length === 0
}
this.size = function () {
return length
}
this.getHead = function () {
return head
}
}
let list = new LinkedList()
list.append(1)
list.append(2)
console.log(list.toString()) // 1 2
list.insert(0, 'hello')
list.insert(1, 'world')
console.log(list.toString()) // hello world 1 2
list.remove(1)
list.remove(2)
console.log(list.toString()) // hello world
深圳,18
,但是有很多条这种数据金钱乱了年纪,大棚乱了四季
hashTable
的put
方法.做防止重复处理,我们这里使用分离链接的方法,配合单链表~ // 修改和增加元素
put(key, value) {
const position = HashTable.loseloseHashCode(key);
console.log(`${position} - ${key}`);
//如果存在就直接在链表头部
if (this.table[position]) {
console.log(this.table[position].toString(), 1);
this.table[position].insert(0, value);
} else {
//否则新建一个单链表,作为这个hashTable中key对应的value
const list = new LinkedList();
list.append(value);
console.log(list.toString(), 2);
this.table[position] = list;
}
}
const hash = new HashTable();
hash.put('深圳', 69);
hash.put('深圳', 96);
console.log(hash.get('深圳').getHead(), 33);
arr.forEach(item => {
hash.put(Object.keys(item)[0], item[Object.keys(item)[0]]);
});
console.log(hash.get('深圳').getHead(),hash.get('深圳').size());
undefined
(如果没有) getGoodLuck = function(num) {
const data = [];
hash.table.forEach((list, index) => {
let count = 0;
let item = list.getHead();
for (let i = 0; i < list.size(); i++) {
count++;
count === num && data.push({ item, index });
item = item.next;
}
});
return data;
};
console.log(getGoodLuck(7));
// 修改和增加元素
put(key, value) {
const position = HashTable.loseloseHashCode(key);
console.log(key, '------', position);
//如果存在就直接在链表头部
if (this.table[position]) {
this.table[position].insert(0, value);
} else {
//否则新建一个单链表,作为这个hashTable中key对应的value
const list = new LinkedList();
list.append(value);
this.table[position] = list;
}
}
console.log(getGoodLuck(6), 6);
console.log(getGoodLuck(9), 9);