📄 hashtablemap-header.html
字号:
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre><font color = #ff0080>/** A hash table with linear probing and the MAD hash function */</font><font color=#ff8000>import</font> java.util.Iterator;<font color=#8000a0>public</font> <font color=#8000a0><font color=#ff8000>class</font> </font>HashTableMap<K,V> <font color=#8000a0><font color=#ff8000>implements</font> </font>Map<K,V> { <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>static</font> <font color=#8000a0><font color=#ff8000>class</font> </font>HashEntry<K,V> <font color=#8000a0><font color=#ff8000>implements</font> </font>Entry<K,V> { <font color=#8000a0><font color=#8000a0>protected</font> </font>K key; <font color=#8000a0><font color=#8000a0>protected</font> </font>V value; <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#0000ff>HashEntry</font>(K k, <font color=#8000a0>V </font>v) { key = k; value = v; } <font color=#8000a0><font color=#8000a0>public</font> </font>V <font color=#0000ff>getValue</font>() { <font color=#8000a0><font color=#ff8000>return</font> </font>value; } <font color=#8000a0><font color=#8000a0>public</font> </font>K <font color=#0000ff>getKey</font>() { <font color=#8000a0><font color=#ff8000>return</font> </font>key; } <font color=#8000a0><font color=#8000a0>public</font> </font>V <font color=#0000ff>setValue</font>(V val) { <font color=#8000a0>V </font>oldValue = value; value = val; <font color=#8000a0><font color=#ff8000>return</font> </font>oldValue; } <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>boolean</font> <font color=#0000ff>equals</font>(Object o) { HashEntry<K,V> ent; <font color=#ff8000>try</font> { ent =<font color=#0000ff> </font>(HashEntry<K,V>) o; } <font color=#ff8000>catch</font><font color=#0000ff> </font>(ClassCastException ex) { <font color=#8000a0><font color=#ff8000>return</font> </font>false; } <font color=#ff8000>return</font><font color=#0000ff> </font>(ent.<font color=#0000ff>getKey</font>() == key) &&<font color=#0000ff> </font>(ent.<font color=#0000ff>getValue</font>() == value); } } <font color=#8000a0><font color=#8000a0>protected</font> </font>Entry<K,V> AVAILABLE = <font color=#8000a0><font color=#ff8000>new</font> </font>HashEntry<K,V><font color=#0000ff></font>(null, null); <font color=#ff0080>// marker </font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>int</font> n = 0; <font color=#ff0080>// number of entries in the dictionary</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>int</font> capacity; <font color=#ff0080>// capacity of the bucket array</font> <font color=#8000a0><font color=#8000a0>protected</font> </font>Entry<K,V>[] bucket;<font color=#ff0080>// bucket array</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>int</font> scale, shift; <font color=#ff0080>// the shift and scaling factors</font> <font color = #ff0080>/** Creates a hash table with initial capacity 1023. */</font> <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#0000ff>HashTableMap</font>() { <font color=#ff8000>this</font><font color=#0000ff></font>(1023); } <font color = #ff0080>/** Creates a hash table with the given capacity. */</font> <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#0000ff>HashTableMap</font>(<font color=#8000a0>int</font> cap) { capacity = cap; bucket =<font color=#0000ff> </font>(Entry<K,V>[]) <font color=#8000a0><font color=#ff8000>new</font> </font>Entry[capacity]; <font color=#ff0080>// safe cast</font> java.util.Random rand = <font color=#8000a0><font color=#ff8000>new</font> </font>java.util.<font color=#0000ff>Random</font>(); scale = rand.<font color=#0000ff>nextInt</font>(capacity-1) + 1; shift = rand.<font color=#0000ff>nextInt</font>(capacity); } <font color = #ff0080>/** Determines whether a key is valid. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>void</font> <font color=#0000ff>checkKey</font>(K k) { <font color=#ff8000>if</font><font color=#0000ff> </font>(k == null) <font color=#8000a0><font color=#ff8000>throw</font> </font><font color=#ff8000>new</font> <font color=#0000ff>InvalidKeyException</font>(<font color=#008000>"Invalid key: null."</font>); } <font color = #ff0080>/** Hash function applying MAD method to default hash code. */</font> <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>int</font> <font color=#0000ff>hashValue</font>(K key) { <font color=#8000a0><font color=#ff8000>return</font> </font>Math.<font color=#0000ff>abs</font>(key.<font color=#0000ff>hashCode</font>()*scale + shift) % capacity; }</dl></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -