資料結構-哈希表 學習筆記
散清單(又稱散列映射,字典,關聯數組)是一種用于以常數平均時間執行插入,删除,查找的技術。
應用:常用于查找;做緩存。
Java代碼實作:
/**
* 非線性存儲結構: 哈希表
*
* @see java.util.Hashtable
* @see java.util.HashMap
*
*/
public class HashTable<E> {
/** 預設容量 */
private static final int DEFAULT_CAPACITY = 1 << 4;
/** 最大容量 */
private static final int MAX_CAPACITY = 1 << 16;
/** 負載因子 */
private static final double DEFAULT_LOAD_FACTOR = 0.75;
/** 内部連結清單數組 */
private Node<E>[] table;
/** 負載因子 */
private final double loadFactor;
/** 觸發表重算的門檻值(threshold = capacity * loadfactor) */
private int threshold;
/** 哈希表的大小 */
private int size = 0;
/** 構造 */
@SuppressWarnings("unchecked")
public HashTable(int initialCapacity, double loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity:" + initialCapacity);
if (initialCapacity > MAX_CAPACITY)
initialCapacity = MAX_CAPACITY;
if (loadFactor <= 0 || Double.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor:" + loadFactor);
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int) (capacity * loadFactor);
table = new Node[threshold]; //
}
/** 構造 */
public HashTable(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 構造 */
@SuppressWarnings("unchecked")
public HashTable() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Node[DEFAULT_CAPACITY]; //
}
/** 添加資料 */
public boolean add(E e) {
int pos = hash(e) % table.length;
Node<E> b = table[pos];
if (b == null) {
table[pos] = new Node<>(hash(e), e, null);
} else {
while (b.next != null)
b = b.next;
b.next = new Node<>(hash(e), e, null);
}
if (size++ >= threshold) //
resize(table.length * 2);
return true;
}
/** 删除資料 */
public boolean remove(Object o) {
int h = hash(o) % table.length;
Node<E> b = table[h];
if (b == null)
return false;
if (b.value.equals(o)) {
if (b.next == null) {
table[h] = null;
} else {
table[h] = b.next;
}
size--;
return true;
} else {
while (b.next != null) {
Node<E> c = b;
b = b.next;
if (b.value.equals(o)) {
c.next = b.next;
size--;
return true;
}
}
}
return false;
}
/** 查找資料 */
public boolean contains(Object e) {
int p = hash(e) % table.length;
Node<E> o = table[p];
if (o == null)
return false;
if (!o.value.equals(e)) {
while (o.next != null) {
o = o.next;
if (o.value.equals(e))
return true;
}
} else {
return true;
}
return false;
}
/** 重算内部連結清單數組的大小,完成擴容 */
@SuppressWarnings("unchecked")
void resize(int newCapacity) {
Node<E>[] old = table;
int oldCapacity = old.length;
if (oldCapacity == MAX_CAPACITY) {
threshold = MAX_CAPACITY;
return;
}
threshold = (int) (newCapacity * loadFactor);
Node<E>[] newTable = new Node[newCapacity];
transfer(newTable);
table = newTable;
}
/** 将擴容前表的資料 複制到新表中 */
void transfer(Node<E>[] newTable) {
Node<E>[] src = table;
int newCapacity = newTable.length;
for (int n = 0; n < src.length; n++) {
Node<E> e = src[n];
if (e != null) {
src[n] = null;
do {
Node<E> next = e.next;
int i = e.hash % newCapacity; // 擴容後獲得資料在哈希表中新的存儲位置
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
/* 連結清單實作 */
static final class Node<E> {
final int hash; // 哈希值
final E value; // 資料
Node<E> next; // 上一個節點
Node(int hash, E value, Node<E> next) {
this.hash = hash;
this.next = next;
this.value = value;
}
@Override
public int hashCode() {
return Objects.hashCode(value);
}
@Override
public boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Node) {
Node<?> b = (Node<?>) o;
if (Objects.equals(value, b.value))
return true;
}
return false;
}
public String toString() {
return value.toString();
}
}
/** 疊代器 */
class HashIterator implements Iterator<Node<E>> {
Node<E> next; // 下一個
int index; // 位置
Node<E> current; // 目前節點
HashIterator() {
if (size > 0) {
Node<E>[] t = (Node<E>[]) table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
@Override
public boolean hasNext() {
return next != null;
}
@Override
public Node<E> next() {
Node<E> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Node<E>[] t = (Node<E>[]) table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
}
/** 獲得疊代器 */
public Iterator<Node<E>> iterator() {
return new HashIterator();
}
/** */
static final class HashSpliterator<E> implements Spliterator<E> {
HashSpliterator() {
}
@Override
public boolean tryAdvance(Consumer<? super E> action) {
return false;
}
@Override
public Spliterator<E> trySplit() {
return null;
}
@Override
public long estimateSize() {
return 0;
}
@Override
public int characteristics() {
return 0;
}
}
@Override
public int hashCode() {
int h = 0;
Iterator<Node<E>> i = iterator();
while (i.hasNext())
h += Objects.hashCode(i.next().value);
return h;
}
@Override
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof HashTable))
return false;
HashTable<?> t = (HashTable<?>) o;
if (t.size() != size())
return false;
Iterator<?> i = t.iterator();
while (i.hasNext()) {
Node<?> n = (Node<?>) i.next();
if (!contains(n.value))
return false;
}
return true;
}
/** 哈希函數:确定資料在HashTable數組中的位置 */
public static final int hash(Object o) {
return o == null ? 0 : Objects.hashCode(o);
}
/** 傳回哈希表的大小 */
public int size() {
return size;
}
/** 字元串輸出 */
public String toString() {
StringBuilder s = new StringBuilder();
s.append('{');
for (int a = 0; a < table.length; a++) {
if (table[a] != null) {
s.append(table[a].value).append(',');
Node<E> e = table[a].next;
while (e != null) {
s.append(e.value).append(',');
e = e.next;
}
}
}
int len = s.length();
if (s.lastIndexOf(",") == len - 1)
s.deleteCharAt(len - 1);
return s.append('}').toString();
// Iterator<E> i = iterator();
// if (!i.hasNext())
// return "{}";
// StringBuilder s = new StringBuilder();
// s.append('{');
// for (;;) {
// s.append(i.next());
// if (!i.hasNext())
// return s.append('}').toString();
//
// s.append(',').append(' ');
// }
}
}
注: