哈希表
思路：一个数组存多个链表 - 当存东西进入时，根据东西的特性将其添加到某个数组链表中，查找元素时，根据东西特性进行从数组中某个链表进行查找
Student.java
public class Student {
Integer id;
String name;
Integer year;
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getYear() {
return year;
}
public void setYear(Integer year) {
this.year = year;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
", year=" + year +
'}';
}
}
MyLinkededList.java
public class MyLinkededList<T> {
Node<T> head = null;
// 添加链表节点
public boolean add(T t) {
//将数据封装成链表节点
Node<T> newNode = new Node<T>();
newNode.setData(t);
//判断当前链表中是否存在相同ID号的特征节点，存在则添加元素失败
Integer id = newNode.getId();
T queryT = this.query(id);
if(queryT != null) {
return false;
}
//添加链表节点
//头元素
if (head == null) {
head = newNode;
//非头元素
} else {
Node<T> tempNode = head;
while (true) {
if (tempNode.next == null) {
tempNode.next = newNode;
break;
}
tempNode = tempNode.next;
}
}
return true;
}
public T query(Integer id) {
if (head == null) {
return null;
} else {
Node<T> curNode = head;
while (true) {
int tId;
try {
tId = curNode.getId();
if (tId == id)
return curNode.getData();
} catch (Exception e) {
e.printStackTrace();
}
curNode = head.getNext();
if (curNode == null) {
break;
}
}
}
return null;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
Node<T> curNode = head;
boolean flag = false;
while (true) {
if (curNode == null) {
if (flag) {
int start = sb.lastIndexOf(", ");
sb.replace(start, sb.length(), "");
}
break;
}
flag = true;
sb.append(curNode.getData() + ", ");
curNode = curNode.getNext();
}
sb.append("]");
return sb.toString();
}
//内置类 - 即链表节点
private class Node<T> {
T data;
Node<T> next;
//
public Integer getId() {
Integer id = null;
try {
Field field = data.getClass().getDeclaredField("id");
field.setAccessible(true);
id = (Integer) field.get(data);
}catch(Exception e) {
e.printStackTrace();
}
return id;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
}
MyHashTable.java
public class MyHashTable<T> {
//默认表容器
private final int DEFAULT_SIZE = 10;
//当前使用的表容器
private int curSize = 10;
//链表数组
MyLinkededList<T>[] lists;
MyHashTable() {
this.lists = new MyLinkededList[DEFAULT_SIZE];
}
MyHashTable(int size) {
curSize = size;
this.lists = new MyLinkededList[curSize];
}
//添加元素 - 如果链表中已经存在特征即相同ID号则添加失败
public boolean add(T t) {
Integer id = null;
try {
id = (Integer) t.getClass().getDeclaredField("id").get(t);
} catch (Exception e) {
e.printStackTrace();
}
int index = id % curSize;
if (lists[index] == null) {
lists[index] = new MyLinkededList<T>();
}
MyLinkededList<T> list = lists[index];
return list.add(t);
}
//根据东西特征即ID号进行查询元素
public T query(Integer id) {
int index = id % curSize;
if (lists[index] == null) {
return null;
}
return lists[index].query(id);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
int index = 0;
for(MyLinkededList list : lists) {
if(list != null) {
sb.append("第" + index + "链表的内容为：" + list + "\n");
}
index++;
}
sb.replace(sb.length()-1, sb.length(), "");
return sb.toString();
}
public static void main(String[] args) {
Student student = new Student();
student.setId(1);
student.setName("lrc");
student.setYear(23);
Student student2 = new Student();
student2.setId(2);
student2.setName("lcj");
student2.setYear(26);
Student student3 = new Student();
student3.setId(12);
student3.setName("yth");
student3.setYear(27);
Student student4 = new Student();
student4.setId(12);
student4.setName("ythfdsfsdf");
student4.setYear(272);
MyHashTable<Student> hashTable = new MyHashTable<>();
hashTable.add(student);
hashTable.add(student2);
hashTable.add(student3);
hashTable.add(student4);
System.out.println(hashTable);
System.out.println(hashTable.query(12));
System.out.println(hashTable.query(100));
}
}
