发布时间:2023-10-10 12:30
学习笔记:coderwhy的JavaScript实现数据结构与算法的课程
其他章节笔记链接
1. 重要性
2. 线性结构
3. 哈希表【本文】
4. 树结构
5. 图结构
6. 排序和搜索
<!DOCTYPE html>
<html lang=\"en\">
<head>
<meta charset=\"UTF-8\">
<title>封装集合</title>
</head>
<body>
<script>
// 封装集合类
function Set() {
// 属性
this.items = {} // 使用了js的object对象
// 方法
// add 方法
Set.prototype.add = function (value) {
// 判断集合中是否已经包含了该元素
if(this.has(value)){
return false; // 添加失败
}else {
// 将元素添加到集合中
this.items[value] = value; // 这里是把属性和属性值都设置为要添加的元素
return true;
}
} ;
// has方法
Set.prototype.has = function (value) {
return this.items.hasOwnProperty(value);
};
// remove方法
Set.prototype.remove = function (value) {
// 1. 该集合中是否包含该元素
if(!this.has(value)){
return false;
}else{
// 2. 将元素从属性中删除
delete this.items[value];
return true;
};
};
// clear 方法
Set.prototype.clear = function () {
this.items = {}
};
// size方法
Set.prototype.size = function () {
return Object.keys(this.items).length;
};
// 获取集合中所有的值
Set.prototype.values = function () {
return Object.keys(this.items); // 获取object中的所有key
}
};
// 测试Set类
// 1. 创建Set类对象
var set = new Set();
// 2. 添加元素
alert(set.add(\'abc\'));
alert(set.add(\'abc\'));
alert(set.add(\'cba\'));
alert(set.add(\'nba\'));
alert(set.add(\'mba\'));
alert(set.values());
// 3. 删除元素
alert(set.remove(\'mba\'));
alert(set.remove(\'mba\'));
alert(set.values());
// 4. has方法
alert(set.has(\'abc\'));
alert(set.has(\'aaabc\'));
// 5. 获取元素的个数
alert(set.size());
// 6. clear 方法
set.clear();
alert(set.size());
</script>
</body>
</html>
// 并集
Set.prototype.union = function (otherSet) {
// this:集合对象A
// otherSet: 集合对象B
// 1. 创建新的集合
var unionSet = new Set();
// 2. 将A集合中的所有元素添加到新集合中
var values = this.values();
for (var i = 0; i < values.length; i++){
unionSet.add(values[i]);
};
// 3. 取出B集合中的元素,判断是否需要加到新集合
values = otherSet.values();
for (var i = 0; i < values.length; i++){
unionSet.add(values[i]);
};
return unionSet;
};
// 交集
Set.prototype.intersection = function (otherSet) {
// this:集合对象A
// otherSet: 集合对象B
// 1. 创建新的集合
var interSet = new Set();
// 2, 从A中取出一个个元素,判断是否同时存在于集合B中,存在放入新集合中
var values = this.values();
for (var i = 0; i < values.length; i++){
var item = values[i];
if (otherSet.has(item)){
interSet.add(item);
}
};
return interSet;
};
(3)代码实现
// 差集
Set.prototype.difference = function (otherSet) {
// this:集合对象A
// otherSet: 集合对象B
// 1. 创建新的集合
var differSet = new Set();
// 2, 从A中取出一个个元素,判断是否不存在于集合B中,存在放入新集合中
var values = this.values();
for (var i = 0; i < values.length; i++){
var item = values[i];
if (!otherSet.has(item)){
differSet.add(item);
}
};
return differSet;
}
(3)代码实现
// 子集
Set.prototype.subset = function (otherSet) {
// this:集合对象A
// otherSet: 集合对象B
// 判断集合A是不是集合B的子集
// 遍历集合A中所有的元素,如果发现,集合A中的元素,在集合B中不存在,那么false
// 如果遍历完成整个集合,依然没有返回false,那么返回true即可
var values = this.values();
for (var i = 0; i < values.length; i++){
var item = values[i];
if (!otherSet.has(item)){
return false;
}
};
return true;
};
是基于数组实现的,但是比起数组又有自己的优势
(1)数组进行插入操作时,效率比较低
(2)数组进行查找操作的效率
1)若是基于索引进行查找效率非常高
2)若是基于内存去查找(比如name=‘why’),效率非常低
(3)数组进行删除操作,效率也不高。
将大数字转化成数组范围内的下标的过程。
将单词转化成大数字,大数字在进行哈希化的代码实现放在一个函数中,这个函数称之为哈希函数。
最终将数据插入到的这个数组,对整个结构的封装, 称之为一个哈希表。
// 设计哈希函数
// 1. 将字符串转换成比较大的数字:hasCode
// 2. 将大的数字hasCode压缩到数组范围之内
function hashFunc(str,size){
// 1. 定义hasCode变量
var hasCode = 0;
// 2. 霍纳算法,来计算hasCode的值
// cats -> Unicode编码
for (var i = 0; i < str.length; i++){
hasCode = 37 * hasCode + str.charCodeAt(i);
};
// 3. 取余操作
var index = hasCode % size;
return index;
}
// 测试哈希函数
alert(hashFunc(\'abc\',7)); // 4
alert(hashFunc(\'cba\',7)); // 3
alert(hashFunc(\'nba\',7)); // 5
alert(hashFunc(\'mba\',7)); // 1
<!DOCTYPE html>
<html lang=\"en\">
<head>
<meta charset=\"UTF-8\">
<title>哈希表实现</title>
</head>
<body>
<script>
// 封装哈希表类
function HashTable() {
// 属性
this.storage = []; // 所有元素的都是放到这个数组中
this.count = 0; // 记录哈希表当前存放的数字个数,用来计算装载因子(loadFactor)
// loadFactor > 0.75 需要对数组进行扩容
// loadFactor < 0.25 需要对数组进行缩小
this.limit = 0 ; // 用于记录数组的长度
// 方法
// 哈希函数
HashTable.prototype.hashFunc = function(str,size){
// 1. 定义hasCode变量
var hasCode = 0;
// 2. 霍纳算法,来计算hasCode的值
// cats -> Unicode编码
for (var i = 0; i < str.length; i++){
hasCode = 37 * hasCode + str.charCodeAt(i);
};
// 3. 取余操作
var index = hasCode % size;
return index;
};
// 插入&修改操作
HashTable.prototype.put = function (key,value) {
// 1. 根据key获取对应的index
var index = this.hashFunc(key,this.limit);
// 2. 根据index取出对应的bucket
var bucket = this.storage[index];
// 3. 判断该bucket还是否为null
if (bucket == null){
bucket = [];
this.storage[index] = bucket;
};
// 4. 判断是否是修改数据
for (var i = 0; i < bucket.length; i++){
var 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. 根据key获取对应的index
var index = this.hashFunc(key,this.limit);
// 2. 根据index取出对应的bucket
var bucket = this.storage[index];
// 3. 判断该bucket还是否为null
if (bucket == null){
return null;
};
// 4. 有bucket,那么就进行线性查找
for (var i = 0; i < bucket.length; i++){
var tuple = bucket[i];
if(tuple[0] == key){
return tuple[1];
};
};
// 5. 依然没有找到, 那么返回null
return null;
};
// 删除操作
HashTable.prototype.remove = function (key) {
// 1. 根据key获取对应的index
var index = this.hashFunc(key,this.limit);
// 2. 根据index取出对应的bucket
var bucket = this.storage[index];
// 3. 判断该bucket还是否为null
if (bucket == null){
return null;
};
// 4. 有bucket,那么就进行线性查找,并且删除
for (var i = 0; i < bucket.length; i++){
var tuple = bucket[i];
if(tuple[0] == key){
bucket.splice(i,1);
this.count--;
return tuple[1];
};
};
// 5. 依然没有找到, 那么返回null
return null;
};
// 其他方法
// 判断哈希表是否为空
HashTable.prototype.isEmpty = function (){
return this.count == 0;
};
// 获取哈希表中元素的个数
HashTable.prototype.size = function (){
return this.count ;
};
}
// 测试哈希表
// 1. 创建哈希表
var ht = new HashTable();
// 2. 插入数据
ht.put(\'abc\',\'123\');
ht.put(\'cba\',\'321\');
ht.put(\'nba\',\'521\');
ht.put(\'mba\',\'520\');
// 3. 获取数据
alert(ht.get(\'abc\'));
// 4. 修改方法
ht.put(\'abc\',\'111\');
alert(ht.get(\'abc\'));
// 5. 删除方法
ht.remove(\'abc\');
alert(ht.get(\'abc\'));
</script>
</body>
</html>
(2) 扩容的方法
(3) 什么情况下进行扩容
(4)代码实现
// 哈希表的扩容/缩容
HashTable.prototype.resize = function (newLimit) {
// 1. 保存旧的数组内容
var oldStorage = this.storage;
// 2. 重置所有的属性
this.storage = [];
this.count = 0;
this.limit = newLimit;
// 3. 遍历oldStorage中所有的bucket
for (var i = 0; i < oldStorage.length; i++){
// 3.1 取出对应的
var bucket = oldStorage[i];
// 3.2 判断bucket是否为null
if (bucket == null){
continue;
}
// 3.3 bucket中有数据,那么取出数据,重新插入
for (var j = 0 ;j <bucket.length; j++){
var tuple = bucket[j];
this.put(tuple[0],tuple[1]);
}
};
}
—————————————————————————————————————————
如果我的文章能帮你节约20秒,就请你为我的文章点个赞吧!