根据尚硅谷韩顺平老师教程。
根据学习可知哈希表的结构大致如下
HashTab.png
完整代码见底部
HashTab
可以看出在哈希表中用数组方式存储了(size个)链表的头结点。
class HashTab{
int size;
Node[] nodes;
}
每一个node存储在哪条链表中的选择是根据 散列函数:num % size;
size是创建HashTab是确定的数据。而num则来自于node中的属性。
根据所学教程,num来自于node中的id。
public int hashIndex(int id){
return id % size;
}
由此在插入node时
可知 node 应插入哪一条链表
public void insertNode(Node node){
if (node == null)
return;
int i = hashIndex(node.getId());
nodes[i].insertNode(node);
}
在已知id的情况下获取信息时
可知当前id应存在于哪一条链表,遍历比对即可获取信息。
public Node findNode(int id){
int i = hashIndex(id);
return nodes[i].findNode(id);
}
Node
根据所学所创建的Node中包含
Id,name,next指针
class Node{
Node next;
int id;
String name;
}
在插入数据时,从应插入数据的链表的头结点开始,开始遍历,出现null即在此条链表中插入数据。
public void insertNode(Node node) {
Node p = this;
while (p.next != null)
p = p.next;
p.next = node;
}
获取数据类似
public Node findNode(int id) {
if (this.next == null)
return null;
Node p = this.next;
while (p != null){
if (p.getId() == id)
return p;
p = p.next;
}
return null;
}
完整代码
HashTab
class HashTab{
int size;
Node[] nodes;
public HashTab(int size) {
this.size = size;
this.nodes = new Node[size];
// 创建头结点。
for (int i = 0; i < size; i++) {
nodes[i] = new Node();
}
}
// 插入node
public void insertNode(Node node){
if (node == null)
return;
int i = hashIndex(node.getId());
nodes[i].insertNode(node);
}
// 散列函数
public int hashIndex(int id){
return id % size;
}
// 显示整个表信息
public void listHashTab(){
for (int i = 0; i < size; i++) {
nodes[i].listNodeList(i);
}
}
// 查询node
public Node findNode(int id){
int i = hashIndex(id);
return nodes[i].findNode(id);
}
}
Node
class Node{
Node next;
int id;
String name;
public Node(int id, String name) {
this.id = id;
this.name = name;
}
public Node() {
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
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;
}
@Override
public String toString() {
return "Node{"+"id=" + id +
", name='" + name + '\'' +
'}';
}
public void insertNode(Node node) {
Node p = this;
while (p.next != null)
p = p.next;
p.next = node;
}
// 显示整个表信息
public void listNodeList(int i) {
System.out.print(i);
Node p = this.next;
while (p != null){
System.out.print("--->");
System.out.print(p);
p = p.next;
}
System.out.println();
}
public Node findNode(int id) {
if (this.next == null)
return null;
Node p = this.next;
while (p != null){
if (p.getId() == id)
return p;
p = p.next;
}
return null;
}
}
测试
public class HashReview {
public static void main(String[] args) {
// 新建hash表 指定hash表的大小
HashTab hashTab = new HashTab(5);
// 手动新建几个需要插入的节点。
Node ss = new Node(1, "ss");
Node cc = new Node(2, "cc");
Node zz = new Node(3, "zz");
Node qq = new Node(8, "qq");
hashTab.insertNode(ss);
hashTab.insertNode(cc);
hashTab.insertNode(zz);
hashTab.insertNode(qq);
// 输出hash表
hashTab.listHashTab();
System.out.println(hashTab.findNode(8));
}
}
网友评论