We use here symbol table based on linked list (class SequentialSearchST<Key, Value>), and building such linked list for every hash, so we have array of linked lists
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SeparateChainingHashSTExample { class SeparateChainingHashST<Key,Value> { private static int INIT_CAPACITY = 4; private int n; // number of key-value pairs private int m; // hash table size private SequentialSearchST<Key, Value>[] st; // array of linked-list symbol tables /** * Initializes an empty symbol table. */ public SeparateChainingHashST() { m = INIT_CAPACITY; } /** * Initializes an empty symbol table with {@code m} chains. * @param m the initial number of chains */ public SeparateChainingHashST(int m) { this.m = m; st = new SequentialSearchST<Key, Value>[m]; for (int i = 0; i < m; i++) st[i] = new SequentialSearchST<Key, Value>(); } // resize the hash table to have the given number of chains, // rehashing all of the keys private void resize(int chains) { SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains); for (int i = 0; i < m; i++) { foreach (Key key in st[i].keys()) { temp.put(key, st[i].get(key)); } } this.m = temp.m; this.n = temp.n; this.st = temp.st; } // hash value between 0 and m-1 private int hash(Key key) { return (key.GetHashCode()& 0x7fffffff) % m; } /** * Returns the number of key-value pairs in this symbol table. * * @return the number of key-value pairs in this symbol table */ public int size() { return n; } /** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public bool isEmpty() { return size() == 0; } /** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public bool contains(Key key) { if (key == null) throw new ArgumentException("argument to contains() is null"); return get(key) != null; } /** * Returns the value associated with the specified key in this symbol table. * * @param key the key * @return the value associated with {@code key} in the symbol table; * {@code null} if no such value * @throws IllegalArgumentException if {@code key} is {@code null} */ public Value get(Key key) { if (key == null) throw new ArgumentException("argument to get() is null"); int i = hash(key); return st[i].get(key); } public void ConsoleDisplay() { Console.WriteLine("key Value HashKey "); foreach (var key in keys()) Console.WriteLine(key + " " + get(key)+" "+ hash(key)); } /** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) throw new ArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; } // double table size if average length of list >= 10 if (n >= 10 * m) resize(2 * m); int i = hash(key); if (!st[i].contains(key)) n++; st[i].put(key, val); } /** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void delete(Key key) { if (key == null) throw new ArgumentException("argument to delete() is null"); int i = hash(key); if (st[i].contains(key)) n--; st[i].delete(key); // halve table size if average length of list <= 2 if (m > INIT_CAPACITY && n <= 2 * m) resize(m / 2); } // return keys in symbol table as an Iterable public IEnumerable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (int i = 0; i < m; i++) { foreach (Key key in st[i].keys()) queue.Enqueue(key); } return queue; } } } |
SequentialSearchST
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SeparateChainingHashSTExample { public class SequentialSearchST<Key, Value> : IEnumerable<Key> { private int n; // number of key-value pairs private Node first; // the linked list of key-value pairs // a helper linked list data type private class Node { public Key key { get; set; } public Value val { get; set; } public Node next { get; set; } public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } } /** * Initializes an empty symbol table. */ public SequentialSearchST() { } /** * Returns the number of key-value pairs in this symbol table. * * @return the number of key-value pairs in this symbol table */ public int size() { return n; } /** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public bool isEmpty() { return size() == 0; } /** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public bool contains(Key key) { if (key == null) throw new ArgumentException("argument to contains() is null"); return get(key) != null; } /** * Returns the value associated with the given key in this symbol table. * * @param key the key * @return the value associated with the given key if the key is in the symbol table * and {@code null} if the key is not in the symbol table * @throws IllegalArgumentException if {@code key} is {@code null} */ public Value get(Key key) { if (key == null) throw new ArgumentException("argument to get() is null"); for (Node x = first; x != null; x = x.next) { if (key.Equals(x.key)) return x.val; } return default(Value); } /** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) throw new ArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; } for (Node x = first; x != null; x = x.next) { if (key.Equals(x.key)) { x.val = val; return; } } first = new Node(key, val, first); n++; } /** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void delete(Key key) { if (key == null) throw new ArgumentException("argument to delete() is null"); first = delete(first, key); } // delete key in linked list beginning at Node x // warning: function call stack too large if table is large private Node delete(Node x, Key key) { if (x == null) return null; if (key.Equals(x.key)) { n--; return x.next; } x.next = delete(x.next, key); // recursion return x; } // iteraror System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator<Key> GetEnumerator() { var node = first; while (node != null) { yield return node.key; node = node.next; } } // public void ConsoleDisplay() { Console.WriteLine(); Console.WriteLine("key" + " " + "val"); for (Node n = first; n != null; n = n.next) { Console.WriteLine(" " + n.key + " " + n.val); } } /** * Returns all keys in the symbol table as an {@code Iterable}. * To iterate over all of the keys in the symbol table named {@code st}, * use the foreach notation: {@code for (Key key : st.keys())}. * * @return all keys in the symbol table */ public IEnumerable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (Node x = first; x != null; x = x.next) queue.Enqueue(x.key); return queue; } } } |
Test client
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SeparateChainingHashSTExample { class Program { static void Main(string[] args) { string[] a = { "S", "E", "A", "R", "C", "H", "E", "X", "A", "M", "P", "L", "E" }; SeparateChainingHashST<string, int> st = new SeparateChainingHashST<string, int>(10); for (int i = 0; i < a.Length; i++) { st.put(a[i], i); } //what is inside? st.ConsoleDisplay(); Console.Read(); } static int hash(string s) { int a = 0x7FFFFFFF; return (s.GetHashCode() * a % 5); } } } |
Ещё вариант
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class SeparateChainsHashST<Key, Value> { private int M; // size of hash table private SequentalSearchST<Key, Value>[] st; public SeparateChainsHashST(int M) { this.M = M; st = new SequentalSearchST<Key, Value>[M]; for (int i = 0; i < M; i++) st[i] = new SequentalSearchST<Key,Value>(); } public int Hash(Key key) { return key.GetHashCode(); } public Value Get(Key key) { return st[Hash(key)].Get(key); } public void Put(Key key, Value val) { st[Hash(key)].Put(key, val); } public IEnumerable<Key> Keys() { Queue<Key> q = new Queue<Key>(); for (int i = 0; i < M; i++) { foreach (Key key in st[i].Keys()) { q.Enqueue(key); } } return q; } } |