-
Java数据结构与算法———(55)创建一个哈希表
2020-07-23 13:32:10有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的 所有信息。要求: 不使用数据库,尽量节省... 创建一个哈希表 HashTab hashTab = new Ha有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的 所有信息。要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)。
一、代码
import java.util.Scanner; public class HashTableDemo { public static void main(String[] args) { // 1. 创建一个哈希表 HashTab hashTab = new HashTab(7); // 2. 测试菜单,根据用户的输入操作 String key = ""; Scanner scanner = new Scanner(System.in); while(true) { System.out.println("add:添加雇员"); System.out.println("list:显示雇员"); System.out.println("find:查找雇员"); System.out.println("exit:退出系统"); key = scanner.next(); switch(key) { case "add": //接收用户输入的信息 System.out.println("输入雇员id:"); int id = scanner.nextInt(); System.out.println("输入名字:"); String name = scanner.next(); //创建雇员 Emp emp = new Emp(id, name); //将雇员加入到HashTab中 hashTab.add(emp); break; case "list": //调用哈希表的list方法 hashTab.list(); break; case "exit": scanner.close(); System.exit(0); break; case "find": System.out.println("请输入要查找的id:"); id = scanner.nextInt(); hashTab.findEmpById(id); break; default: break; } } } } // 1. 创建HashTab,管理多条链表 class HashTab{ // 1. 声明一个链表数组empLinkedListArray,这个链表数组的每个元素里面存放的都是链表 private EmpLinkedList[] empLinkedListArray; private int size;//表示共有多少条链表,即数组的大小 // 2. 构造器 public HashTab(int size) { this.size = size; //初始化empLinkedListArray empLinkedListArray = new EmpLinkedList[size]; // 这里有一个坑!!! // 一定要分辨初始化每条链表 for (int i = 0; i < size; i++) { empLinkedListArray[i] = new EmpLinkedList(); } } // 3. 添加雇员 public void add(Emp emp) { // 根据雇员的id,得到该员工应当添加到哪条链表 int empLinkedListNo = hashFun(emp.id); // 将emp添加到对应的那条链表 empLinkedListArray[empLinkedListNo].add(emp); } // 4. 编写一个散列函数,使用简单取模法 //这个散列函数的作用,就是通过输入雇员id,找到该雇员听该放到哪条聊表 public int hashFun(int id) { return id % size; } // 5. 遍历链表数组中的每条链表,即遍历哈希表 public void list() { //共有size条链表 for(int i = 0; i < size; i++) { empLinkedListArray[i].list(i); } } // 6. 根据输入的id,查找雇员 public void findEmpById(int id) { int empLinkedListNo = hashFun(id); Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id); if(emp != null) { System.out.printf("该雇员在第%d条链表\n", hashFun(emp.id));; }else { System.out.println("没有找到"); } } } // 2. 编写一个Emp类,表示雇员,一个雇员相当于一个链表的节点 class Emp{ // 1. 定义属性 public int id; public String name; public Emp next;//next默认为 null // 2. 定义构造器 public Emp(int id, String name) { this.id = id; this.name = name; } } // 3. 编写一个EmpLinkedList,表示链表,里面存放雇员信息 class EmpLinkedList{ // 1. 定义一个头指针,指向第一个Emp,因此这个链表的head是直接指向链表的第一个节点 private Emp head;//默认为null // 2. 添加雇员到链表 // 说明 // 1. 当添加雇员时, id是自增长的,即id得分配总是从小到大 // 2. 因此新得雇员总是添加到链表最后 public void add(Emp emp) { // 1. 当添加得是第一个雇员(节点) if(head == null) { //注意:head是头指针,是直接指向链表得第一个节点,当head==null时,就说明链表为空;当 head!=null时,说明链表非空,因为head指向了链表得第一个节点 head = emp; return; } // 2. 当添加的不是第一个节点时 //定义一个辅助指针,用来定位到链表最后 Emp temp = head; //遍历链表,让temp指向最后一个节点 while(true) { //当找到最后一个节点就退出循环 if(temp.next == null) {//表示到了链表最后 break; } //没到链表最后,就就继续遍历 temp = temp.next; } //退出while循环后,temp就指向了最后一个节点 temp.next = emp; } // 3. 显示链表(遍历输出每个节点) public void list(int no) { // 1. 空链表,退出方法 if(head == null) {//注意:head是指针,不是节点,指针是指向某一个节点 System.out.printf("第%d条链表为空\n", no); return; } // 2. 链表非空,遍历输出 Emp temp = head;//定义一个辅助指针temp,与head指向同一个对象(节点) System.out.printf("第%d条链表的信息:", no); while(true) { // 1. 判断是否到达链表最后 if(temp == null) { break;//输出完毕,退出循环 } // 2. 没到最后,输出 System.out.printf("-->id = %d name = %s\t", temp.id, temp.name); temp = temp.next; } //输出完一条链表后就换行 System.out.println(); } // 4.根据id查找雇员 // 如果查到,就返回Emp;如果没有查到,就返回null public Emp findEmpById(int id) { // 1. 先判断链表是否为空 if (head == null) { System.out.println("链表为空"); return null;// } // 2. 链表非空 Emp temp = head; while(true) { // 1. 退出循环的条件 if(temp == null) {//到达链表最后,且没有找到该雇员 break;//退出循环 } // 2. 不退出循环,继续找 // 找到了 if(temp.id == id) { break;//此时temp已经指向了要找的雇员 } //没找到 temp = temp.next;//后移 } return temp; } }
二、结果
add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 0 输入名字: jack add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 1 输入名字: lusi add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 2 输入名字: tom add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 3 输入名字: nana add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 4 输入名字: lulu add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 5 输入名字: tick add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 6 输入名字: mark add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 7 输入名字: allen add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入雇员id: 8 输入名字: jordan add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 lsit add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 list 第0条链表的信息:-->id = 0 name = jack -->id = 7 name = allen 第1条链表的信息:-->id = 1 name = lusi -->id = 8 name = jordan 第2条链表的信息:-->id = 2 name = tom 第3条链表的信息:-->id = 3 name = nana 第4条链表的信息:-->id = 4 name = lulu 第5条链表的信息:-->id = 5 name = tick 第6条链表的信息:-->id = 6 name = mark add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 find 请输入要查找的id: 0 该雇员在第0条链表 add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 find 请输入要查找的id: 8 该雇员在第1条链表 add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 find 请输入要查找的id: 2 该雇员在第2条链表 add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统
-
创建一个简单的哈希表
2019-09-14 12:42:04class HashTable: def __init__(self, size): self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法 self.count = size # 最大表长 def hash(self, key): return key...class HashTable: def __init__(self, size): self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法 self.count = size # 最大表长 def hash(self, key): return key % self.count # 散列函数采用除留余数法 def insert_hash(self, key, value): """插入关键字到哈希表内""" address = self.hash(key) # 求散列地址 while self.elem[address]: # 当前位置已经有数据了,发生冲突。 address = (address + 1) % self.count # 线性探测下一地址是否可用 self.elem[address] = value # 没有冲突则直接保存。 def search_hash(self, key): """查找关键字,返回布尔值""" star = address = self.hash(key) while self.elem[address] != key: address = (address + 1) % self.count if not self.elem[address] or address == star: # 说明没找到或者循环到了开始的位置 return False return True if __name__ =="__main__": hash1=HashTable(7) hash1.insert_hash(1,11) hash1.insert_hash(2,12) hash1.insert_hash(3,13) hash1.insert_hash(4,14) print(hash1.search_hash(14))
-
17. 哈希表,以及如何创建哈希表,哈希表可以做缓存
2020-10-16 19:36:59也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含...1. 什么是哈希表
- 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
- 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
代码实现
package com.qin.hashtable; import java.util.Scanner; public class HashTableDemo { public static void main(String[] args) { //创建一个hash表 HashTab hashTab = new HashTab(7); //写一个简单的菜单 Scanner scanner = new Scanner(System.in); String key = " "; boolean loop = true; while (loop){ System.out.println("add 添加一个雇员"); System.out.println("list 遍历所有雇员"); System.out.println("exit 结束观察"); System.out.println("find 查找雇员"); System.out.println("del 根据id删除雇员"); key = scanner.next(); switch (key){ case "add": System.out.println("输入id"); int id = scanner.nextInt(); System.out.println("输入名字"); String name =scanner.next(); //创建雇员 Emp emp = new Emp(id, name); hashTab.add(emp); break; case "list": hashTab.list(); break; case "find": System.out.println("请输入要查找的id"); id = scanner.nextInt(); hashTab.findEmpById(id); break; case "del": System.out.println("请输入要删除的id"); id = scanner.nextInt(); hashTab.deleteEmpById(id); break; case "exit": scanner.close(); loop = false; break; default: break; } } System.out.println("gg"); } } //表示一个雇员 class Emp{ public int id; public String name; public Emp next; //next默认为空 //有参构造 public Emp(int id, String name) { this.id = id; this.name = name; } } //创建一个E冒泡LinkedList,表示一条链表 class EmpLinkedList{ //头指针,指向第一个Emp,因此我们这个链表的head是直接指向第一个雇员的 private Emp head; //默认为null //添加雇员到链表 //我们直接将该雇员加到本链表的最后一个即可 public void add(Emp emp){ //如果是添加第一个雇员 if (head==null){ //直接把需要加入的emp赋值给head head = emp; return; } //如果不是第一个雇员,就使用一个辅助指针帮我们找到最后 Emp cur = head; while (true){ if (cur.next==null){ //说明到链表的最后了,需要结束循环 break; } cur =cur.next; //后移 } //退出时,直接将emp挂载到cur后面 cur.next = emp; } //遍历链表雇员信息 public void list(int no){ if (head == null){ //说明当前链表为空 System.out.println("第"+(no+1)+"链表为空"); return; } System.out.printf("第%d链表的信息为",no+1); Emp cur = head; //辅助指针 while (true){ System.out.printf("=> id=%d name = %s \t",cur.id,cur.name); if (cur.next==null){ //说明是最后一个,结束循环 break; } cur = cur.next; //后移 } System.out.println(); } //根据id查找雇员 //如果查找到就返回Emp,如果没有找到就返回null public Emp findEmpById(int id){ //判断链表是否为空 if (head==null){ System.out.println("链表为空"); return null; } //辅助指针 Emp cur = head; while (true){ if (cur.id==id){ //说明这个时候就找到了 break; } if (cur.next==null){ //说明已经到了最后了 cur = null; break; } cur = cur.next;//后移 } return cur; } //删除雇员 public void deleteEmpById(int id){ //辅助指针 Emp cur = head; if (head==null){ //说明链表为空 System.out.println("链表为空,无法删除"); return; } while (true){ if (head.id == id){ head = head.next; return; } if (cur.next==null){ break; } if (cur.next.id==id){ cur.next = cur.next.next; return; }else { System.out.println("找不到要删除的id"); } cur = cur.next; } } } //编写hashTable 管理多条链表 class HashTab{ //创建一个单链表的数组,每个数组都是一个单链表 private EmpLinkedList[] empLinkedListArray; private int size; //表示有多少条链表 //构造器 public HashTab(int size) { this.size =size; empLinkedListArray = new EmpLinkedList[size]; //分别初始化每个链表 for (int i = 0; i < size ; i++) { empLinkedListArray[i] = new EmpLinkedList(); } } //添加雇员 public void add(Emp emp){ //根据员工的id,得到该员工应该添加到哪条链表 int empLinkedListNo = hashFun(emp.id); //将emp添加到对应的链表中 empLinkedListArray[empLinkedListNo].add(emp); } //编写一个散列函数,使用简单的取模 public int hashFun(int id){ return id % size; } //遍历所有的链表 public void list(){ for (int i = 0; i < size; i++) { empLinkedListArray[i].list(i); } } //根据id查找emp public void findEmpById(int id){ //使用散列函数确定在哪条链表查找 int empLinkedListNo = hashFun(id); Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id); if (emp==null){ System.out.println("没有这个雇员"); }else { //找到了 System.out.println("在第"+(empLinkedListNo+1)+"找到了该雇员,雇员id="+emp.id+",名字name="+emp.name); } } //删除雇员 public void deleteEmpById(int id){ //使用散列函数确定在哪条链表查找 int empLinkedListNo = hashFun(id); empLinkedListArray[empLinkedListNo].deleteEmpById(id); System.out.println("删除成功"); } }
- 结果
-
姓名哈希表创建哈希表,将ASCII码取余得KEY值,若未发生冲突存入哈希表
2020-06-24 16:12:08/为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法... -
JavaScript创建哈希表
2013-04-22 16:19:51本例通过JavaScript创建一个哈希表,学习如何保存数据字典(键/值对)。 【实现代码】 标题页 //自定义哈希表类 function Hashtable() { this._hash = new Object(); // 创建Object对象 //哈希表的添加...【实例描述】
在保存数据时,使用哈希表可以存储不同数据类型的值。本例通过JavaScript创建一个哈希表,学习如何保存数据字典(键/值对)。
【实现代码】
<html xmlns="http://www.w3.org/1999/xhtml" > <head> <title>标题页</title> <SCRIPT LANGUAGE="JavaScript"> //自定义哈希表类 function Hashtable() { this._hash = new Object(); // 创建Object对象 //哈希表的添加方法 this.add = function(key,value){ if(typeof(key)!="undefined"){ if(this.contains(key)==false){ this._hash[key]=typeof(value)=="undefined"?null:value; return true; } else { return false; } } else { return false; } } //哈希表的移除方法 this.remove = function(key){delete this._hash[key];} //哈希表内部键的数量 this.count = function(){var i=0;for(var k in this._hash){i++;} return i;} //通过键值获取哈希表的值 this.items = function(key){return this._hash[key];} //在哈希表中判断某个值是否存在 this.contains = function(key){ return typeof(this._hash[key])!= "undefined";} //清空哈希表内容的方法 this.clear = function(){for(var k in this._hash){delete this._hash[k];}} } var myhash=new Hashtable(); //创建哈希表 myhash.add("name","张三"); //添加键和值 if(myhash.contains("name")) //判断是否存在name键 alert(myhash.items("name")); //根据指定name键显示哈希表的值 </script> </head> <body> </body> </html>
http://88688lin.blog.163.com/blog/static/110248187200842714939261/
-
如何创建和使用哈希表
2004-12-02 10:38:00如何创建和使用哈希表本示例阐释如何创建和使用哈希表。哈希表是由键-值组合构成的集合,组织到"存储桶"中以供快速搜索。可以通过键或关联的值搜索哈希表;...当填充哈希表时,为它提供一个要添加到表中的键,并提供伴 -
实现OPEN哈希表模板类,用哈希表实现一个英语词典
2020-11-19 13:49:44在经过哈希函数变换后,可能将不同关键码映射到同一个哈希地址上。对此处理的方法有开放定址法、链地址法和再哈希法。 我们所用到的是开发定值法:构建哈希表先要创建哈希函数,常用的哈希函数方法为除留余数法: H... -
哈希表的创建
2015-10-06 22:28:56在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和表中唯一的存储位置相对应,称这个对应关系f为哈希(散列)函数,根据这个思想建立的表为哈希表。 若key1≠key2, 而f(key1)=f(key2), 则... -
哈希表创建以及哈希表迭代hasNext()与next()方法理解
2020-07-15 20:38:03哈希表既是一种查找方法,又是一种存贮方法。我们通常再查找过程中希望能够不经过任何比较,一次便能得到所查记录。不过这是理想状态下。 哈希表:即散列存储结构。 散列法存储的基本思想:建立关键码字与其存储位置... -
用c++创建一个最简单的哈希表(拉链法)
2018-12-26 23:43:15我们都知道,当我们要在一个集合中查找数据时,如果这个集合是顺序表且我们能确定要找的数据在顺序表中的位置的话,我们就能通过下标直接找到元素,这无非是我们要追求的最高效的查找策略!但是现实总是那么骨感,在... -
python建立哈希表_如何在python中为大数据创建哈希表?
2020-12-23 14:43:02文本文件可能有重复项,这将覆盖字典中现有的键(哈希表的python名称)。您可以创建一组唯一的键,然后使用字典理解来填充字典。在样本_文件.txtabccPython代码^{pr2}$这是一个包含100万个长度为10的随机字母字符的... -
哈希表之二----链地址法创建哈希表
2014-05-10 15:04:32解决哈希表地址冲突的一个 -
哈希表创建 (C语言(icoding
2020-07-09 16:41:42哈希表创建 哈希表(Hash Table,也叫散列表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。... -
哈希表一
2016-12-16 10:04:33一、定义哈希表(散列表)通过将关键码映射...创建哈希表时,把关键字为 k 的元素 直接存入地址为 f(k) 的单元 ;以后当查找关键字为 k 的元素时,再利用哈希函数计算出该元素的存储位置 p=f(k) ,从而达到按关键 字直接 -
哈希表
2019-11-13 18:53:22每个顺序表的节点在单独引出一个链表 二、添加数据 计算哈希码 计算在哈希表中的存储位置 存入哈希表 情况1:一次添加成功 情况2:多次添加成功(出现了冲突,调用equals()和对应链表的元素进行比较,... -
python第一个只出现一次的字符哈希表
2020-12-03 19:24:57python第一个只出现一次的字符哈希表题目描述题解代码 题目描述 ...hashmap = dict() # 创建一个字典 for i in s : if i not in hashmap: hashmap[i] = True # 如果该元素第一次出现,则设对应布尔值为T -
C++实现的一个哈希表类
2008-01-09 13:20:00头文件:/*----------------------------------------------------------------// ...//// 文件名:Hash.h// 文件功能描述:此类简单实现了一个hash表的功能//// 作者:Sundy// 创建标识:2005-06-27////-------- -
C++实现的一个哈希表类
2007-11-17 12:03:00*----------------------------------------------------------------// ... //// 文件名:Hash.h// 文件功能描述:此类简单实现了一个hash表的功能//// 作者:Sundy// 创建标识:2005-06-27////----------------- -
哈希表数据结构_图文并茂详解数据结构之哈希表
2020-12-04 15:54:40哈希表简介哈希表也叫散列表,哈希表是一种数据结构,它提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,插入和查找的时间复杂度都是为O...哈希表采用的是一种转换思想,其中一个中要的概念是如何将「...
收藏数
1,651
精华内容
660