📄 hashtablemap-linear2.html
字号:
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre> <font color = #ff0080>/** Put a key-value pair in the map, replacing previous one if it exists. */</font> <font color=#8000a0><font color=#8000a0>public</font> </font>V <font color=#0000ff>put </font>(K key, <font color=#8000a0>V </font>value) <font color=#8000a0><font color=#ff8000>throws</font> </font>InvalidKeyException { <font color=#8000a0><font color=#8000a0>int</font> </font>i = <font color=#0000ff>findEntry</font>(key); <font color=#ff0080>//find the appropriate spot for this entry</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(i >= 0) <font color=#ff0080>// this key has a previous value</font> <font color=#ff8000>return</font><font color=#0000ff> </font>(<font color=#0000ff></font>(HashEntry<K,V>) bucket[i]).<font color=#0000ff>setValue</font>(value); <font color=#ff0080>// set new value </font> <font color=#ff8000>if</font><font color=#0000ff> </font>(n >= capacity/2) { <font color=#0000ff>rehash</font>(); <font color=#ff0080>// rehash to keep the load factor <= 0.5</font> i = <font color=#0000ff>findEntry</font>(key); <font color=#ff0080>//find again the appropriate spot for this entry</font> } bucket[-i-1] = <font color=#8000a0><font color=#ff8000>new</font> </font>HashEntry<K,V><font color=#0000ff></font>(key, value); <font color=#ff0080>// convert to proper index</font> n++; <font color=#8000a0><font color=#ff8000>return</font> </font>null; <font color=#ff0080>// there was no previous value</font> } <font color = #ff0080>/** Doubles the size of the hash table and rehashes all the entries. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>void</font> <font color=#0000ff>rehash</font>() { capacity = 2*capacity; Entry<K,V>[] old = bucket; bucket =<font color=#0000ff> </font>(Entry<K,V>[]) <font color=#8000a0><font color=#ff8000>new</font> </font>Entry[capacity]; <font color=#ff0080>// new bucket is twice as big </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; <font color=#ff0080>// new hash scaling factor</font> shift = rand.<font color=#0000ff>nextInt</font>(capacity); <font color=#ff0080>// new hash shifting factor</font> <font color=#ff8000>for</font><font color=#0000ff> </font>(<font color=#8000a0>int</font> i=0; i<old.length; i++) { Entry<K,V> e = old[i]; <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff></font>(e != null) &&<font color=#0000ff> </font>(e != AVAILABLE)) { <font color=#ff0080>// a valid entry</font> <font color=#8000a0><font color=#8000a0>int</font> </font>j = - 1 - <font color=#0000ff>findEntry</font>(e.<font color=#0000ff>getKey</font>()); bucket[j] = e; } } } <font color = #ff0080>/** Removes the key-value pair with a specified key. */</font> <font color=#8000a0><font color=#8000a0>public</font> </font>V <font color=#0000ff>remove </font>(K key) <font color=#8000a0><font color=#ff8000>throws</font> </font>InvalidKeyException { <font color=#8000a0><font color=#8000a0>int</font> </font>i = <font color=#0000ff>findEntry</font>(key); <font color=#ff0080>// find this key first</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(i < 0) <font color=#8000a0><font color=#ff8000>return</font> </font>null; <font color=#ff0080>// nothing to remove</font> <font color=#8000a0>V </font>toReturn = bucket[i].<font color=#0000ff>getValue</font>(); bucket[i] = AVAILABLE; <font color=#ff0080>// mark this slot as deactivated</font> n--; <font color=#8000a0><font color=#ff8000>return</font> </font>toReturn; }} </dl></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -