关于哈希表的一些基础概念就不过多赘述，有意向者自行查阅相关资料！下面说一些注意事项。
1、三种哈希结构：数组、集合（set）、映射（map）
其中集合中没有相同的元素，所以将数据填入集合中有去重的效果。
映射分为
2、当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
3、一些需要快速插入和搜索，可以考虑使用哈希表。
4、下面是根据《java数据结构与算法》一书中对哈希表进行的实现。（并不是很重要，因为现在实现都已经提供了具体的方法）
// 为防止冲突有两种方法解决，，这个是开放地址法
class Solution {
public static void main (String[] args) {
Data aData = new Data(33);
HashTable aHashTable = new HashTable(10);
aHashTable.insert(aData);
Data atData = aHashTable.find(33);
System.out.println(atData.getValue());
}
}
class Data {
int val;
public Data(int v) {
this.val = v;
}
public int getValue() {
return val;
}
}
class HashTable {
// 哈希表大小、哈希表、删除数据时填入的数据
private int tableSize;
private Data[] hashDatas;
private Data noData;
public HashTable(int size) {
tableSize = size;
hashDatas = new Data[tableSize];
noData = new Data(-1);
}
public int hashFuc(int key) {
return key % tableSize;
}
public int hashFuc2(int key) {
return 5 - key % 5;
}
public void insert(Data val) {
int key = val.getValue();
int hashVal = hashFuc(key);
int step = hashFuc2(key);
while (hashDatas[hashVal] != null && hashDatas[hashVal].getValue() != -1) {
key += step;
hashVal = hashFuc(key);
}
hashDatas[hashVal] = val;
}
public void delete(int key) {
int hashVal = hashFuc(key);
int step = hashFuc2(key);
while (hashDatas[hashVal] != null) {
if (hashDatas[hashVal].getValue() == key) {
hashDatas[hashVal] = noData;
return;
}
key += step;
hashVal = hashFuc(key);
}
}
public Data find(int key) {
int hashVal = hashFuc(key);
int step = hashFuc2(key);
while (hashDatas[hashVal] != null) {
if (hashDatas[hashVal].getValue() == key) {
return hashDatas[hashVal];
}
key += step;
hashVal = hashFuc(key);
}
return null;
}
}
// 为防止冲突有两种方法解决，，这个是链地址法
class Solution {
public static void main (String[] args) {
HashTable aHashTable = new HashTable(10);
aHashTable.insert(33);
aHashTable.insert(34);
link alink = aHashTable.find(34);
System.out.println(alink.val);
}
}
class link {
int val;
link next;
link () {}
public link(int v) {
this.val = v;
}
public int getValue() {
return val;
}
}
class linkedList {
link head;
// 记录链表的大小
int size;
linkedList() {
size = 0;
// 创建一个虚拟头结点
head = new link(0);
}
public int get(int index) {
if (index < 0 || size <= index) {
return -1;
}
link currentlink = head;
for (int i = 0; i <= index; i++) {
currentlink = currentlink.next;
}
return currentlink.val;
}
public void addAtIndex(int index, int val) {
// 其实只需要定位要插入节点的前一个就行了
if (index > size)
return;
else if (index <= 0) {
index = 0;
}
link insertNode = new link(val);
link prelink = head;
for (int i = 0; i < index; i++) {
prelink = prelink.next;
}
insertNode.next = prelink.next;
prelink.next = insertNode;
// 注意这个不能忘记
size++;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void deleteAtKey(int key) {
link prelink = head;
link currentlink = prelink.next;
while (currentlink != null) {
if (currentlink.val == key) {
prelink.next = currentlink.next;
return;
}
prelink = prelink.next;
currentlink = currentlink.next;
}
// 这个东西总是容易遗忘
size--;
}
public link findTheKey(int key) {
link prelink = head;
link currentlink = prelink.next;
while (currentlink != null) {
if (currentlink.val == key) {
return currentlink;
}
prelink = prelink.next;
currentlink = currentlink.next;
}
return null;
}
public void display() {
head = head.next;
while (head != null) {
System.out.printf("%d ", head.val);
head = head.next;
}
}
}
class HashTable {
// 哈希表大小、哈希表、删除数据时填入的数据,,,每一个单元由链表组成
private int tableSize;
private linkedList[] hashDatas;
public HashTable(int size) {
tableSize = size;
hashDatas = new linkedList[tableSize];
// 这个不要忘记，定义完链表类型的数组要进行单独的初始化
for (int i = 0; i < tableSize; i++) {
hashDatas[i] = new linkedList();
}
}
public int hashFuc(int key) {
return key % tableSize;
}
public void insert(int key) {
int hashVal = hashFuc(key);
hashDatas[hashVal].addAtIndex(0, key);
}
public void delete(int key) {
int hashVal = hashFuc(key);
hashDatas[hashVal].deleteAtKey(key);
}
public link find(int key) {
int hashVal = hashFuc(key);
return hashDatas[hashVal].findTheKey(key);
}
}
5、接下来非常的重要，几乎在编程时就用到了下面的东西。
// 哈希集合的用法
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
// 1. initialize the hash set
Set hashSet = new HashSet<>();
// 2. add a new key
hashSet.add(3);
hashSet.add(2);
hashSet.add(1);
// 3. remove the key
hashSet.remove(2);
// 4. check if the key is in the hash set
if (!hashSet.contains(2)) {
System.out.println("Key 2 is not in the hash set.");
}
// 5. get the size of the hash set
System.out.println("The size of has set is: " + hashSet.size());
// 6. iterate the hash set
for (Integer i : hashSet) {
System.out.print(i + " ");
}
System.out.println("are in the hash set.");
// 7. clear the hash set
hashSet.clear();
// 8. check if the hash set is empty
if (hashSet.isEmpty()) {
System.out.println("hash set is empty now!");
}
}
}
//哈希映射
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
// 1. initialize a hash map
Map hashmap = new HashMap<>();
// 2. insert a new (key, value) pair
hashmap.putIfAbsent(0, 0);
hashmap.putIfAbsent(2, 3);
// 3. insert a new (key, value) pair or update the value of existed key
hashmap.put(1, 1);
hashmap.put(1, 2);
// 4. get the value of specific key
System.out.println("The value of key 1 is: " + hashmap.get(1));
// 5. delete a key
hashmap.remove(2);
// 6. check if a key is in the hash map
if (!hashmap.containsKey(2)) {
System.out.println("Key 2 is not in the hash map.");
}
// 7. get the size of the hash map
System.out.println("The size of hash map is: " + hashmap.size());
// 8. iterate the hash map
for (Map.Entry entry : hashmap.entrySet()) {
System.out.print("(" + entry.getKey() + "," + entry.getValue() + ") ");
}
System.out.println("are in the hash map.");
// 9. clear the hash map
hashmap.clear();
// 10. check if the hash map is empty
if (hashmap.isEmpty()) {
System.out.println("hash map is empty now!");
}
}
}
一些相关的知识
