投融网站建设方案,网址怎么推广,商城网站开发的完整流程,珠海模板网站建设什么是数据结构#xff1f;
下面是维基百科的解释#xff1a; 数据结构是计算机存储、组织数据的方式。数据结构意味着接口或封装#xff1a;一个数据结构可被视为两个函数之间的接口#xff0c;或者是由数据类型联合组成的存储内容的访问方法封装。 我们每天的编码中都会…什么是数据结构
下面是维基百科的解释 数据结构是计算机存储、组织数据的方式。数据结构意味着接口或封装一个数据结构可被视为两个函数之间的接口或者是由数据类型联合组成的存储内容的访问方法封装。 我们每天的编码中都会用到数据结构下面是常见的数据结构
数组Array栈Stack队列Queue链表Linked List散列表Hash字典树Tree图Graph堆Heap
散列表Hash 散列表Hash是一种常用的数据结构用于存储键值对。它利用散列函数将键映射到一个数字索引上以便快速地插入、删除和查找数据。在JavaScript 中可以使用对象来实现散列表的功能。 特点
快速操作在散列表上插入、删除和取用数据都非常快。低效率查找对于查找操作来说却效率低下。
设计目的
用数组或链表存储数据时若想要找到其中一个数据需要从头进行遍历因为不知道这个数据存储在数组的哪个位置。散列表通过散列函数将键映射为一个数字使得数据存储在特定位置从而提高了查找效率。
JavaScript中的实现
在 JavaScript 中散列表可以基于对象进行设计。数组的长度是预先设定的所有元素根据与该元素对应的键保存在数组的特定位置。这里的键和对象的键是类型的概念。当使用散列表存储数组时通过一个散列函数将键映射为一个数字这个数字的范围是0到散列表的长度。
案例参考
以下是一个使用散列表存储学生信息的案例 HTML/JS 效果其中使用了一个自己实现的散列表实现了基本的插入、删除和查找操作
HTML代码
!DOCTYPE html
html langen
headmeta charsetUTF-8titleStudent Info/title
/head
bodyinput typetext placeholder输入名字 idnameInputinput typetext placeholder输入成绩 idscoreInputbutton onclickaddStudent()添加学生/buttonbrbrinput typetext placeholder输入要搜索的名字 idsearchInputbutton onclicksearchStudent()搜索学生/buttonbrbrlabel forresult结果: /labelspan idresult/spanscript srchashTable.js/script
/body
/htmlJavaScript代码
// 自定义散列函数function hashFunction(key) {var hash 0;for (var i 0; i key.length; i) {hash key.charCodeAt(i);}return hash % 100; // 假设散列表有 100 个位置}// 自定义散列表类function HashTable() {this.table new Array(100); // 创建一个大小为 100 的数组作为散列表this.add function (key, value) {var index hashFunction(key);this.table[index] value;};this.remove function (key) {var index hashFunction(key);this.table[index] undefined;};this.find function (key) {var index hashFunction(key);return this.table[index];};}// 创建一个散列表实例用于存储学生信息var studentHash new HashTable();// 根据输入添加学生信息function addStudent() {var name document.getElementById(nameInput).value;var score document.getElementById(scoreInput).value;studentHash.add(name, score);console.log(studentHash.table);}// 根据输入查找学生的成绩function searchStudent() {var name document.getElementById(searchInput).value;var score studentHash.find(name);if (score ! undefined) {document.getElementById(result).textContent score;} else {document.getElementById(result).textContent 没有找到相关数据;}}上述代码中首先定义了一个散列函数 hashFunction该函数将输入的键通过字符编码相加并取余操作得到散列的索引。然后创建了一个自定义的散列表类 HashTable内部使用一个大小为 100 的数组作为散列表的存储结构。散列表的 add() 方法根据键的散列值将值存储到相应的位置上remove() 方法按键的散列值将相应位置的值置为 undefinedfind() 方法根据键的散列值查找对应的值。
在 HTML 中通过输入框和按钮来添加学生并通过另一个输入框和按钮来查找学生的成绩。在 JS 的实现中添加学生和查找学生都是通过散列表的 add() 和 find() 方法实现的。当添加学生时根据学生的姓名计算出散列值然后将对应的成绩存储到散列表中。当查找学生时根据输入的姓名计算出散列值并在散列表中查找对应的成绩最后将结果在页面上展示出来。
总体来说上述代码实现了使用散列表存储学生信息的基本功能。
散列表Hash中的碰撞解决方法
在散列表中当两个不同的键被映射到相同的位置时就会发生碰撞。为了解决这个问题有两种常见的方法开链法和线性探测法。
1. 开链法
开链法是一种简单而直观的碰撞解决方法。它使用数组来存储散列中的每个槽位每个槽位都是一个链表或者数组。当发生碰撞时新的键值对会被添加到对应槽位的链表或数组上。
示例 假设我们有一个散列表其中包含10个槽位。当发生碰撞时我们将键值对存储在对应槽位的链表或数组中。例如如果键 “apple” 和 “banana” 都被映射到槽位 3并且已经有一个键值对 “apple: red” 存储在该位置上那么 “banana: yellow” 将会被添加到 “apple: red” 后面形成一个链表或数组。
2. 线性探测法
线性探测法是另一种处理碰撞的方法。当发生碰撞时线性探测法会顺序地检查下一个槽位直到找到一个空的槽位来存储新的键值对。
示例 假设我们有一个散列表其中包含10个槽位。当发生碰撞时线性探测法会依次检查下一个槽位直到找到一个空的槽位。例如如果键 “apple” 被映射到槽位 3但该位置已经被占用线性探测法会继续检查槽位 4、5 直到找到一个空的槽位来存储 “apple: red”。
这两种方法提供了灵活的方式来处理散列表中的碰撞确保即使发生碰撞仍然能够有效地存储和检索数据。
开链法Chaining
优点
简单易懂 开链法实现起来比较简单容易理解和实现。适用于大量数据 当数据量很大时开链法能够有效地处理碰撞因为每个槽位都可以容纳多个键值对。
缺点
额外空间开销 使用链表或数组来解决碰撞需要额外的存储空间可能导致内存浪费。性能不稳定 如果链表过长查找某个键的时间复杂度可能变得较高导致性能不稳定。
线性探测法Linear Probing
优点
节省空间 相比开链法线性探测法不需要额外的链表或数组节省了一些空间。缓存友好 连续的存储位置对缓存更友好有助于提高访问效率。
缺点
聚集问题 线性探测法可能导致聚集问题即连续位置上出现大量的键增加了后续插入的冲突概率。删除操作复杂 删除操作相对复杂因为需要保证删除后的位置后面的元素都能正确找到。
如何选择
如果对内存空间要求较高而且对性能的稳定性要求不那么严格可以选择开链法。如果内存空间相对充足而且希望在大规模数据下有更稳定的性能可以选择线性探测法。
总体来说选择开链法还是线性探测法取决于具体应用场景和对性能、内存的不同需求。 持续学习总结记录中回顾一下上面的内容 散列表Hash是一种常用的数据结构用于存储键值对。它利用散列函数将键映射到一个数字索引上以便快速地插入、删除和查找数据。在JavaScript 中可以使用对象来实现散列表的功能。
