HashTable을 Java의 Generic을 이용하여 구현해봤다.
Chain (LinkedList) 를 사용하여 메모리를 필요한 만큼만 생성한다.
Hash 함수는 아주 기본적인 모듈라(%) 연산을 사용하여 작성한다.
모든 자료형을 담을 수 있다.
참고 : Cracking the Coding Interview
class Hash<K, V>
{
private final int MAX_SIZE = 10;
private LinkedList<Cell<K, V>>[] items;
public Hash()
{
items = (LinkedList<Cell<K, V>>[])new LinkedList[MAX_SIZE];
}
//simplified hash function
public int hashCodeOfKey(K key)
{
return key.toString().length() % MAX_SIZE;
}
public void put(K key, V value)
{
int x = hashCodeOfKey(key);
if(items[x] == null)
{
items[x] = new LinkedList<Cell<K, V>>();
}
LinkedList<Cell<K, V>> collided = items[x];
/* if item of same key is existed already
remove existing key and value for new ones */
for(Cell<K, V> c : collided)
{
if(c.equivalent(key))
{
collided.remove(c);
break;
}
}
Cell<K, V> cell = new Cell<K, V>(key, value);
collided.add(cell);
}
public V get(K key)
{
int x = hashCodeOfKey(key);
if(items[x] == null)
{
return null;
}
LinkedList<Cell<K, V>> collided = items[x];
for(Cell<K, V> c : collided)
{
if(c.equivalent(key))
{
return c.getValue();
}
}
return null;
}
}
class Cell<K,V>
{
private K key;
private V value;
public Cell(K k, V v)
{
key = k;
value = v;
}
public boolean equivalent(Cell<K,V> c)
{
return equivalent(c.getKey());
}
public boolean equivalent(K k)
{
return key.equals(k);
}
public K getKey()
{
return key;
}
public V getValue()
{
return value;
}
}
'컴퓨터공학 > Data structure' 카테고리의 다른 글
| Heap (0) | 2013.01.08 |
|---|---|
| Traversing Tree (0) | 2013.01.07 |
| Balance? - Tree (0) | 2013.01.07 |
