2011 6 20 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2011/index.html tech.ac.jp/k1sakai/lecture/alg/2011/index.html html 1
O(1) O(1) 2
(123) () H(k) = k mod n (k:, n: ) 3
4
public class MyHashtable { public MyHashtable(int amaxsize) { this.table = new MyData[aMaxSize]; public MyData get(string akey) { return this.table[this.calculatehashcode(akey)]; public boolean put(mydata amydata) { this.table[this.calculatehashcode(amydata.getname())] = amydata; return true; public boolean remove(string akey) { this.table[this.calculatehashcode(akey)] = null; return true; private int calculatehashcode(string akey) { int intkey = 0; for(int count = 0; count < akey.length(); count++){ intkey += 0xFFFF & akey.charat(count); return intkey % this.table.length; private MyData[] table; 5
6
() 2.7.1 125 7
public class MyData { public MyData(String x) { name = x; private final String name; public String getname() { return name; public boolean equals(object x) { MyData y; try { y = (MyData) x; catch (ClassCastException e) { return false; return this.name.equals(y.getname()); public int hashcode() { int intkey = 0; for (byte e : name.getbytes()) { intkey += e; return intkey; public String tostring() { return name; hashcode() equals() Object 8
public class ChainHashtable<T> { public ChainHashtable(int max_size) { this.table = new List[max_size]; private List<T>[] table; private int hashcode(t data) { int hashcode = Math.abs(data.hashCode()); ()); return hashcode % this.table.length; public boolean put(t data) { int hashcode = hashcode(data); if (this.table[hashcode] == null) this.table[hashcode] = new LinkedList<T>(); this.table[hashcode].add(data); return true; public T get(t data) { List<T> list = this.table[hashcode(data)]; table[hashcode(data)]; if (null == list) return null; for (T e : list) if (e.equals(data)) return e; return null; public boolean remove(t data) { List<T> list = this.table[hashcode(data)]; if (null == list) return false; return list.remove(data); T T T 9
public String tostring() { StringBuffer sb = new StringBuffer(); int index = 0; for (List<T> list : this.table) t { sb.append('[').append(index++).append("]"); if (list!= null) for (T e : list) sb.append(" -> ").append(e.tostring()); ()) sb.append(' n'); return sb.tostring(); private final static String[] test_data = { " ", "", " ", " ", "", " ", " "; public static void main(string args[]) { System.out.println(""); t tl ") ChainHashtable<String> hashtable1 = new ChainHashtable<String>(3); for (String e : test_data) hashtable1.put(e); System.out.print(hashtable1.toString()); System.out.println(" "); t tl ") hashtable1.remove(" "); System.out.print(hashtable1.toString()); [0] -> [1] -> -> -> -> -> [2] -> [0] -> [1] -> -> -> -> [2] -> [0] -> -> [1] -> [2] -> -> -> -> [0] -> -> [1] -> [2] -> -> -> System.out.println(""); t tl ") ChainHashtable<MyData> hashtable2 = new ChainHashtable<MyData>(3); for (String e : test_data) hashtable2.put(new MyData(e)); System.out.print(hashtable2.toString()); System.out.println(" "); tp "); hashtable2.remove(new MyData(" ")); System.out.print(hashtable2.toString()); 10
2.7.4 131 134 11
134 12
public class OpenHashtable<T extends Object> { public OpenHashtable(int max_size) { this.table = new Object[max_size]; private Object[] table; private final static Object removed_data = new Object(); public boolean put(t data) { int hashcode = hashcode(data); for (int count = 0; count < this.table.length; count++) { if ((null == this.table[hashcode]) (removed_data == this.table[hashcode])) { this.table[hashcode] t sh = data; return true; hashcode = hashcode(data, hashcode); return false; 1 public T get(t data) { int hashcode = hashcode(data); for (int count = 0; count < this.table.length; count++) { if (null == this.table[hashcode]) return null; if (removed_data!= this.table[hashcode]) if (this.table[hashcode].equals(data)) return (T) this.table[hashcode]; hashcode = hashcode(data, hashcode); return null; remove, hashcode 13
public boolean remove(t data) { int hashcode = hashcode(data); for (int count = 0; count < this.table.length; count++) { if (null == this.table[hashcode]) t h { return false; if f( (removed _ data!= this.table[hashcode]) { if (this.table[hashcode].equals(data)) { this.table[hashcode] = removed_data; return true; hashcode = hashcode(data, hashcode); return false; private int hashcode(t data) { int hashcode = Math.abs(data.hashCode()); return hashcode % this.table.length; private int hashcode(t data, int hashcode) { int intkey = hashcode(data); return ((hashcode + 3 - (intkey % 3)) % this.table.length); 1 2 1 3 1 14
0: (0) 1: 2: (2) 3: (3) 4: 5: 6: (6) 7: (7) 8: (8) 9: (8) 10: 0: [removed] 1: 2: (2) 3: (3) 4: 5: 6: (6) 7: (7) ( ) 8: (8) 9: (8) 10: String MyData hashcode() 0: 1: (1) 2: (2) 3: (3) 4: 5: (5) ) 6: (5) 7: (7) 8: (8) 9: 10: 0: 1: (1) 2: (2) 3: [removed] 4: 5: (5) 6: (5) 7: (7) ( ) 8: (8) 9: 10: 15
+5 mod 10 16
! +5 mod 11 17
0: (0) 1: 2: (2) 3: (3) 4: 5: 6: (6) 7: (7) 8: (8) 9: (8) 10: String MyData 0: 1: (1) 2: (2) 3: (3) 4: 5: (5) 6: (5) 7: (7) 8: (8) 9: 10: String MyData g y 18