1.哈希查詢算法由兩部分組成
哈希函數将要查詢的鍵(key)轉換成數組的角标。
面對的問題：多個不同的鍵(key)經過hash之後轉換成相同數組角标
有兩種方案解決沖突：各自的鍊(separate chaining)、直線的探測(linear probing)
2.單獨的鍊
兩個或多個鍵經過哈希函數得到相同的角标值。将這些碰撞的項連結到單獨的連結清單中，這種方法稱之為單獨的鍊（separate chaining）。
（1） 通過hash函數發現那個清單包含key；
（2）按照順序清單的順序查詢key；
3.直線的探查
另一個實作哈表的方法是将N個鍵值對存放在一個長度為M（M>N）的哈希表中，依靠表中的空元素項去解決沖突。這樣的方法被稱為**開放尋址(open-addressing)**的哈希方法。
最簡單的開發尋址方法被稱之為直線的探查（linear probing）: 當這兒有一個沖突（通過哈希函數得到的表格角标已經被其他不同的key所占用），那麼我們就需要檢查表格中下一個項（将角标加1）。
**直線的探查（linear probing）**會遇到三種情況：
鍵等于查詢的鍵：鍵存在
空位置（這個角标上沒有鍵）：沒有查到
鍵不等于查詢的鍵：試着查詢下一個
該算法的實作思路如下：
通過哈希函數計算出鍵（key0）所在表格的角标，檢查查詢到的鍵（key）是否和剛做哈希函數的鍵（key0）相等，繼續(通過增加角标，當達到表格結尾的時候就傳回表格的頭)直到查到鍵（key0）或者查到一個空的表格項。
HashFunctionTest.java
package com.hef.algorithms.chapter3.item34;
/**
* @Date 2020/2/5
* @Author lifei
*/
public class HashFunctionTest {
private static final int R = 31;
public static void main(String[] args) {
int s = stringHashTestFive("S");
System.out.println(s);
System.out.println(("S".hashCode()&0x7fffffff)%5);
}
private static int stringHashTestFive(String str){
return stringHashTest(str, 5);
}
private static int stringHashTest(String str, int M){
int hash = 0;
for (int i=0;i<str.length();i++){
hash = (R+str.charAt(i))%M;
}
return hash;
}
}
LinearProbingHashST.java
package com.hef.algorithms.chapter3.item34;
/**
* @Date 2020/2/7
* @Author lifei
*/
public class LinearProbingHashST<Key, Value> {
// number of key-value pairs in the table
private int N;
// size of linear-probing table
private int M = 16;
// the keys
private Key[] keys;
// the values
private Value[] vals;
public LinearProbingHashST(){
keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];
}
private LinearProbingHashST(int cap){
keys = (Key[]) new Object[cap];
vals = (Value[]) new Object[cap];
}
private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
//
private void resize(int cap){
LinearProbingHashST<Key, Value> t;
t = new LinearProbingHashST<>(cap);
for (int i = 0; i < M; i++) {
if (keys[i]!=null){
t.put(keys[i], vals[i]);
}
}
keys = t.keys;
vals = t.vals;
M = t.M;
}
public void put(Key key, Value val){
// double M
if (N >= M/2) resize(2*M);
int i;
for (i = hash(key); keys[i]!=null; i = (i+1) % M) {
if (keys[i].equals(key)){
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
N++;
}
public Value get(Key key){
for (int i=hash(key); keys[i]!=null; i = (i+1)%M){
if (keys[i].equals(key)){
return vals[i];
}
}
return null;
}
public boolean contains(Key key){
for (int i = hash(key); keys[i]!=null; i=(i+1)%M) {
if (keys[i].equals(key)){
return true;
}
}
return false;
}
public void delete(Key key){
if (!contains(key)) return;
int i = hash(key);
while (!key.equals(keys[i])){
i = (i+1)%M;
}
keys[i] = null;
vals[i] = null;
i = (i+1)%M;
while (keys[i]!=null){
Key keyToRedo = keys[i];
Value valToRedo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
put(keyToRedo, valToRedo);
i = (i+1)%M;
}
N--;
if (N>0 && N==M/8) resize(M/2);
}
}
SeparateChainingHashST.java
package com.hef.algorithms.chapter3.item34;
import java.util.Iterator;
/**
* @Date 2020/2/6
* @Author lifei
*/
public class SeparateChainingHashST<Key, Value> {
// number of key-value paris
private int N;
// hash table size
private int M;
// array of ST objects
private SequentialSearchST<Key, Value>[] st;
public SeparateChainingHashST(){
this(997);
}
// Create M linked lists
public SeparateChainingHashST(int M){
this.M = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
for (int i = 0; i < M; i++) {
st[i] = new SequentialSearchST();
}
}
private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
public Value get(Key key){
return (Value) st[hash(key)].get(key);
}
public void put(Key key, Value val){
st[hash(key)].put(key,val);
N++;
}
public Iterable<Key> keys(){
return new KeyIterable();
}
private class KeyIterable implements Iterable<Key>{
@Override
public Iterator<Key> iterator() {
return new KeyIterator();
}
}
private class KeyIterator implements Iterator<Key>{
private int tempIndex = 0;
private Iterator<Key> currentIterator;
public KeyIterator(){
for (int i=0;i<M;i++) {
if (!st[i].isEmpty()){
currentIterator = st[i].keys().iterator();
tempIndex=i;
break;
}
}
}
@Override
public boolean hasNext() {
if (currentIterator==null) return false;
return currentIterator.hasNext();
}
@Override
public Key next() {
Key key = currentIterator.next();
if (!currentIterator.hasNext()){
currentIterator = nextIterator();
}
return key;
}
private Iterator<Key> nextIterator(){
for (int i = tempIndex+1; i < M; i++) {
if (!st[i].isEmpty()){
tempIndex = i;
return st[i].keys().iterator();
}
}
return null;
}
}
public static void main(String[] args) {
SeparateChainingHashST<String, Integer> separateChainingHashST = new SeparateChainingHashST<>();
separateChainingHashST.put("aa",23);
separateChainingHashST.put("world", 12);
separateChainingHashST.put("hello", 33);
Iterable<String> iterable = separateChainingHashST.keys();
Iterator<String> iterator = iterable.iterator();
while (iterator.hasNext()){
String next = iterator.next();
System.out.println(next);
}
}
}
SequentialSearchST.java
package com.hef.algorithms.chapter3.item34;
import java.util.Iterator;
/**
* 順序查詢的key-value 表
*
* @Date 2020/2/6
* @Author lifei
*/
public class SequentialSearchST<Key, Value> {
private Node first;
private class Node {
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
public boolean isEmpty(){
if (first==null) return true;
return false;
}
/**
* Search for key, return associated value
*
* @param key
* @return
*/
public Value get(Key key) {
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
return x.val;
}
}
return null;
}
/**
* Search for key. Update value if found; grow table if new
*
* @param key
* @param val
*/
public void put(Key key, Value val) {
for (Node x = first; x != null; x = x.next) {
// Search hit: update val
if (key.equals(x.key)) {
x.val = val;
return;
}
}
// Search miss: add new node
first = new Node(key, val, first);
}
public Iterable<Key> keys() {
return new KeyIterable();
}
private class KeyIterable implements Iterable<Key> {
@Override
public Iterator<Key> iterator() {
return new KeyIterator();
}
}
private class KeyIterator implements Iterator<Key> {
private Node current = first;
@Override
public boolean hasNext() {
if (current == null) return false;
return true;
}
@Override
public Key next() {
Key key = current.key;
current = current.next;
return key;
}
}
public static void main(String[] args) {
SequentialSearchST<String, Integer> sequentialSearchST = new SequentialSearchST<>();
sequentialSearchST.put("aa", 23);
sequentialSearchST.put("bb", 33);
sequentialSearchST.put("cc", 12);
System.out.println(sequentialSearchST.first.key);
Iterable<String> keys = sequentialSearchST.keys();
Iterator<String> iterator = keys.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
System.out.println(next);
}
}
}
https://github.com/hefrankeleyn/AlgorithmsBook/blob/master/AlgorithmsPro/src/main/java/com/hef/algorithms/chapter3/item34/SequentialSearchST.java
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)