11-哈希表js代码实现

11-哈希表js代码实现

设计哈希函数（目的为返回那个计算好的index）：
// 1> 将字符串转成比较大的数字：hashCode
// 2> 将大的数字hashCode压缩到数组范围(大小)之内
function hashFunction(str, size) {
// 1.定义hashCode变量
let hashCode = 0;

// 2.霍纳算法，来计算hashCode的值。
// 字符串-》 Unicode编码。
for (let i = 0; i < str.length; i++) {
hashCode = 37 hashCode + str.charCodeAt(i);
}

// 3.取余操作
let index = hashCode % size;

return index;
}*

创建哈希表：
此处采用链地址法来实现

哈希表的插入和修改操作时同一个函数：
- 因为，当使用者传入一个的时候：如果原来不存在该key，那么就是插入操作，如果已经存在该key，那么就是修改操作。
代码解析：
- 步骤1：根据传入的key获取对应的hashCode，也就是数组的index。
- 步骤2：从哈希表的index位置中取出另一个数组。
- 步骤3：查看上一步的bucket是否为null。
  - 为null表示之前在该位置没有放置过任何的内容，那么就新建一个数组（其实其它语言如C python有元组数据类型更合适）。
- 步骤4：查看是否之前已经放置过key对应的value。
  - 如果放置过，那么就是依次替换操作，而不是插入新的数据。
  - 我们使用一个变量override来记录是否是修改操作。
- 步骤5：如果不是修改操作，那么插入新的数据。
  - 在bucket中push新的【key，value】即可。
  - 注意：这里需要将count+1，因为数据增加了一项。

实现代码：
// 创建HashTable构造函数
function HashTable() {
// 定义属性

// 作为数组，这个数组中存放相关的元素。
this.storage = [];

// count表示当前已经存在了多少数据。
this.count = 0;

// limit用于标记数组中一共可以存放多少个元素。
this.limit = 7;

// 方法
// 哈希函数
HashTable.prototype.hashFunction = function (str, size) {
// 1.定义hashCode变量
let hashCode = 0;
// 2.霍纳算法，来计算hashCode的值。
// 字符串-》 Unicode编码。
for (let i = 0; i < str.length; i++) {
hashCode = 37 * hashCode + str.charCodeAt(i);
}
// 3.取余操作
let index = hashCode % size;
return index;
}

// 插入&修改操作
HashTable.prototype.put = function (key, value) {
// 1.根据key获取对应的index
let index = this.hashFunction(key, this.limit);

// 2.根据index取出对应的bucket
let bucket = this.storage[index];

// 3.判断该bucket是否为null
if (bucket == null) {
bucket = [];
this.storage[index] = bucket;
}

// 4.判断如果是修改数据
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i];
if (tuple[0] == key) {
tuple[1] = value;
return;// 如果是添加怎么到此结束。
}
}

// 5.进行添加操作
bucket.push([key, value]);
this.count += 1;
}

// 获取操作
HashTable.prototype.get = function (key) {
// 1 先获取这个hash下标
let index = this.hashFunction(key, this.limit);
// 2 判断是否存在
let bucket = this.storage[index];
let tuple = null;
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
tuple = bucket[i];
if (tuple[0] == key) { // 2.1 存在则返回
return tuple[1];
}
}
}
// 2.2 否则返回null
return null;
}

// 删除操作
HashTable.prototype.remove = function (key) {
// 1 获取这个hash下标
let index = this.hashFunction(key, this.limit);
// 2 判断是否存在
let bucket = this.storage[index];
let tuple = null;
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
tuple = bucket[i];
if (tuple[0] == key) {
bucket.splice(i, 1); // 2.1 存在则删除,count减一，并返回。
this.count -= 1;
return tuple[1];
}
}
}
// 2.2 否则返回null
return null;
}

// 其它方法
// 判断这个哈希表是否为null
HashTable.prototype.isEmpty = function () {
return this.count == 0;
}
// 获取哈希表中元素的个数
HashTable.prototype.size = function () {
return this.count;
}
}

let ht = new HashTable();**

js数据结构整理笔记 learning...

11 哈希表js代码实现

11-哈希表js代码实现