【数据结构与算法】8、哈希表 图解、代码实现
程序员文章站
2022-04-24 12:46:20
...
1、题目要求
- 看一个实际需求,google公司的一个上机题:
- 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址.),当输入该员工的id时,要求查找到该员工的所有信息.
- 要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
2、哈希表的基本介绍
散列表(Hash table 也叫哈希表) 是根据关键码值(key value)而直接进行访问的数据结构,也就是说,他通过把关键码映射到表中的一个位置来进行访问,以加快查询的速度。这个映射函数叫做散列函数,记录存放的的数据 也叫散列表。
3、图解
4、代码实现
package com.hblg.hashtable;
/**
* @author i
* @create 2019/10/12 10:04
* @Description 哈希表
*/
public class HashTableDemo {
public static void main(String[] args) {
HashTable hashTable = new HashTable(10);
//添加
hashTable.add(new Student(1,"张三","电大"));
hashTable.add(new Student(12,"李四","武大"));
hashTable.add(new Student(22,"李四2","华科"));
hashTable.add(new Student(32,"李四3","清华"));
hashTable.add(new Student(52,"李四5","山大"));
hashTable.add(new Student(11,"李四6","中南"));
hashTable.add(new Student(21,"李四7","贝丽达"));
hashTable.add(new Student(31,"李四8","武大"));
hashTable.delete(31);
hashTable.uodate(new Student(1,"张三","华北理工"));
hashTable.printList();
}
}
/***
*
*/
class HashTable{
private StudentLinkedList [] studentLinkedList = null;
private int size;
public HashTable(int size){
this.size = size;
studentLinkedList = new StudentLinkedList [size];
//必须进行初始化
for (int i = 0; i < size ; i++) {
studentLinkedList[i] = new StudentLinkedList();
}
}
//添加
public void add(Student student){
if (student!=null){
int index = hash(student.getId());
studentLinkedList[index].add(student);
}else {
throw new NullPointerException("数据为空!");
}
}
//遍历
public void printList(){
for (int i = 0; i < studentLinkedList.length; i++) {
studentLinkedList[i].printList();
}
}
//查找
public void findStudentById(int id){
//先找到对应的数组
int index = hash(id);
studentLinkedList[index].find(id);
}
//删除
public void delete(int id){
int index = hash(id);
studentLinkedList[index].delete(id);
}
//修改
public void uodate(Student student){
int index = hash(student.getId());
studentLinkedList[index].uodateStudentById(student);
}
//散列函数
private int hash(int id){// 2%3 2
return id%size;
}
}
/***
* 单链表
*/
class StudentLinkedList{
private Student head;//头结点
//添加
public void add(Student student){
if(head == null){//当前链表head为空
head = student;
return;
}
Student currentNode = head;
//遍历获取链表的最后
while (true){
if(currentNode.next == null){
break;
}
//遍历
currentNode = currentNode.next;
}
currentNode.next = student;
}
//遍历
public void printList(){
if (head == null){
System.out.println("链表为空");
return;
}
Student studentNode = head;//获取到头结点 进行遍历
while (true){
System.out.print("id:"+studentNode.getId()+" name:"+studentNode.getName()+" school:"+studentNode.getSchool()+"\t ->");
if(studentNode.next==null){
break;
}
studentNode = studentNode.next;
}
System.out.println();
}
//查找
public void find(int id){
if (head == null){
throw new NullPointerException("linkedList is null!");
}
Student currentNode = head;
while (true){
if(currentNode.getId() == id){//找到
System.out.println("find it is info :"+currentNode);
break;
}
if (currentNode.next == null){//遍历到链表最后
System.out.println("没有找到");
break;
}
currentNode = currentNode.next;
}
}
//删除
public void delete(int id){
if(head == null){
throw new RuntimeException("没有找到");
}
Student currentNode = head;
while (true){
if(currentNode.next.getId() == id){
currentNode.next = currentNode.next.next;
break;
}
if(currentNode.next == null){
System.out.println("没有找到");
break;
}
currentNode = currentNode.next;
}
}
//修改 根据id修改用户信息
public void uodateStudentById(Student student){
if (head == null){
throw new RuntimeException("没有找到");
}
Student currentNode = head;
while (true){
if(currentNode.getId() == student.getId()){
currentNode.setName(student.getName());
currentNode.setSchool(student.getSchool());
System.out.println("currentNode:"+currentNode);
System.out.println("student:"+student);
break;
}
if(currentNode.next == null){
System.out.println("没有找到");
break;
}
currentNode = currentNode.next;
}
}
}
/***
* id
* name
* school
*/
class Student{
private int id;
private String name;
private String school;
Student next;
public Student() {
}
public Student(int id,String name, String school) {
this.name = name;
this.id = id;
this.school = school;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getSchool() {
return school;
}
public void setSchool(String school) {
this.school = school;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
", school='" + school + '\'' +
'}';
}
}
推荐阅读
-
死磕数据结构与算法——哈希表(java实现)。才疏学浅,如有错误,及时指正
-
数据结构与算法之顺序表C语言实现
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
python算法与数据结构-二叉树的代码实现(46)
-
年轻人要学算法,一定会用到的Java常用的8种排序算法与代码实现
-
Java 数据结构与算法:递归实现八皇后问题、思路分析、代码实现
-
Java数据结构与算法:单向环形链表、约瑟夫问题、思路分析、代码实现
-
数据结构与算法1:二叉树(binary_tree)的前、中、后序(深度优先)和广度优先遍历及python代码实现
-
数据结构与算法-哈希表
-
【数据结构与算法-C语言版】顺序表(线性表的顺序存储结构)及C语言实现