哈希表
1.什么是哈希表?
哈希表是一种数据结构,它提供了快速的插入操作和查找操作。其基于数组来实现。
2.哈希化
1)直接将关键字作为索引。
2)将单词转换成索引。
<1>将字母转换成ASCII码,然后进行相加
<2>幂的连乘
<3>压缩可选值
3.压缩后仍然可能出现的问题。
冲突:不能保证每个单词都映射到数组的空白单元。
解决办法:
<1>开放地址法
<2>链地址法
/**
* 员工信息类
* @author Administrator
*
*/
public class Info {
private String key;
private String name;
public Info(String key, String name) {
this.key = key;
this.name = name;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
import java.math.BigInteger;
public class HashTable {
private Info[] arr;
/**
* 默认的构造方法
*/
public HashTable() {
arr = new Info[100];
}
/**
* 指定数组初始化大小
*/
public HashTable(int maxSize) {
arr = new Info[maxSize];
}
/**
* 插入数据
*/
public void insert(Info info) {
arr[hashCode(info.getKey())] = info;
}
/**
* 查找数据
*/
public Info find(String key) {
return arr[hashCode(key)];
}
public int hashCode(String key) {
// int hashVal = 0;
// for(int i = key.length() - 1; i >= 0; i--) {
// int letter = key.charAt(i) - 96;
// hashVal += letter;
// }
// return hashVal;
BigInteger hashVal = new BigInteger("0");
BigInteger pow27 = new BigInteger("1");
for(int i = key.length() - 1; i >= 0; i--) {
int letter = key.charAt(i) - 96;
BigInteger letterB = new BigInteger(String.valueOf(letter));
hashVal = hashVal.add(letterB.multiply(pow27));
pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
}
return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
}
}
public class TestHashTable {
public static void main(String[] args) {
HashTable ht = new HashTable();
ht.insert(new Info("a","张三"));
ht.insert(new Info("ct","李四"));
ht.insert(new Info("wangwu","王五"));
System.out.println(ht.find("a").getName());
System.out.println(ht.find("ct").getName());
}
}
分享到:
相关推荐
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
数据结构(Java语言描述) 单元设计_单元8 哈希表.doc 学习资料 复习资料 教学资源
讲解哈希函数,哈希表的原理以及常用运算。 是常用的数据结构
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
数据结构学习笔记(5)——使用draw.io绘制的映射、哈希表和跳跃表图,详细绘制了映射、哈希表和跳跃表图,使用draw.io——免费开源的画图工具。
JAVA数据结构与算法课程第05课双端链表和双向链表.mp4JAVA数据结构与算法...哈希表.mp4JAVA数据结构与算法课程第16课开放地址法.mp4JAVA数据结构与算法课程第17课链地址法.mp4JAVA数据结构与算法课程第18课图的基本概念...
java 实现常用数据结构(链表,集合,栈,哈希表,搜索,排序等).
包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
java java_leetcode面试题解哈希表第170题数据结构设计_题解
哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希表经典讲解+各项优化+分析哈希...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
介绍了计算机编程中使用的...《Java数据结构和算法》(第2版)提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程,在学生掌握了编程的基础后才开始本书的学习。
线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util包中。本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用...
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
public class HashTabDemo { public static void main(String[] args) { HashTab hashTab = new HashTab(7); String key = ""; Scanner scanner = new Scanner(System.in); while (true){ ...
在本篇文章里小编给大家分享了关于java数据结构和算法中哈希表的相关知识点内容,需要的朋友们学习下。
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
包含链表、 栈、 队列、优先级队列、哈希表,绝对原创总结!