음하하하

[Clone Graph]

https://leetcode.com/problems/clone-graph/

[Copy List with Random Pointer]

https://leetcode.com/problems/copy-list-with-random-pointer/

HashTable, BFS를 이용하여 푼다.

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;
	}
}