Hash哈希表 散列表
哈希表
哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
为什么要使用哈希表?首先我们来看下数组和链表的特点:
- 数组:查询(寻址)易,操作(插入、删除)难。
- 链表:查询(寻址)难,操作(插入、删除)易。
那我们能不能综合这两者的优点,创建一个查询(寻址)容易同时操作(插入、删除)也容易的数据结构?
答案就是哈希表,它能兼顾数组和链表的优点。
哈希表存储数据的结构图:
该图左边是一个数组,每个数组存储内容指向一个链表。
散列函数
散列函数,能将一个元素根据该函数转换为哈希表的数组下表。
散列函数的常见实现方式:
- 除法散列表,即将元素的关键码除以一个固定的数求摩。
index = key % p
- 平方散列法
- 斐波那契散列法
下面代码用除法散列法的方式实现一个哈希表:
public class User {
private int id;
private String name;
private User next;
public User() {}
public User(int id, String name) { this.id = id; this.name = name; }
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 User getNext() { return next; }
public void setNext(User next) { this.next = next; }
@Override
public String toString() { return "User [id=" + id + ", name=" + name + "]"; }
}
public class UserLinkedList {
private int index; // 当前列表在哈希表中的索引
private User head; // 指向头结点
public UserLinkedList(int index) {
this.index = index;
head = new User();
}
// 添加数据
public void add(User user) {
if(null == head.getNext()) {
head.setNext(user);
return ;
}
User tmp = head;
while(null != tmp.getNext()) {
tmp = tmp.getNext();
}
tmp.setNext(user);
}
// 查找数据
public User find(int userId) {
if(null == head.getNext()) {
return null;
}
User result = null;
User tmp = head.getNext();
while(null != tmp) {
if(userId == tmp.getId()) {
result = tmp;
break ;
}
tmp = tmp.getNext();
}
return result;
}
// 打印数据
public void print() {
if(null == head.getNext()) {
System.err.printf("第%d条链表为空!\n", index + 1);
return ;
}
System.out.printf("第%d条链表:", index + 1);
User tmp = head.getNext();
while(null != tmp) {
System.out.print(tmp + "\t");
tmp = tmp.getNext();
}
System.out.println();
}
}
public class HashTable {
private int size;
private UserLinkedList[] userLinkedLists;
public HashTable(int size) {
super();
this.size = size;
this.userLinkedLists = new UserLinkedList[size];
for(int i = 0; i < size; i++) {
userLinkedLists[i] = new UserLinkedList(i);
}
}
// 散列函数
private int hash(int userId) {
return userId % size;
}
// 添加数据
public void add(User user) {
int index = hash(user.getId());
userLinkedLists[index].add(user);
}
// 查找数据
public User find(int userId) {
int index = hash(userId);
return userLinkedLists[index].find(userId);
}
// 打印数据
public void print() {
for(int i = 0; i < size; i++) {
userLinkedLists[i].print();
}
}
}
public class HashTableDemo {
public static void main(String[] args) {
HashTable hashTable = new HashTable(7);
Scanner scanner = new Scanner(System.in);
String key = null;
boolean loop = true;
while(loop) {
System.out.println("a(add)添加数据");
System.out.println("f(find)查找数据");
System.out.println("p(print)打印数据");
System.out.println("e(exit)退出");
key = scanner.next();
switch(key) {
case "a":
System.out.println("请输入用户编号:");
int userId = scanner.nextInt();
System.out.println("请输入用户名称:");
String userName = scanner.next();
hashTable.add(new User(userId, userName));
break ;
case "f":
System.out.println("请输入要查找的用户id");
int findVal = scanner.nextInt();
User findUser = hashTable.find(findVal);
if(null == findUser) {
System.err.printf("查找的用户id:%d不存在!\n", findVal);
} else {
System.out.println("查找的用户:" + findUser);
}
break ;
case "p":
hashTable.print();
break ;
case "e":
loop = false;
scanner.close();
break;
default:
break;
}
}
}
}