Hash & HashTable Algorithm 설명 및 구현

해쉬 알고리즘이란??

키 값을 입력 받아서 해쉬 테이블의 주소가 되는 값을 반환해주는 함수

해쉬 테이블이란??

Key & Value로 이루어진 테이블 형태의 자료 구조로서 Key값이 Hash 함수를 거쳐 나온 Hash 값을 테이블 상의 저장 주소로 사용한다. 

해쉬 값은 최대한 중복이 발생 되지 않는게 좋겠지만 현실적으로 불가능 하며 이것을 해결 하기 위한 방법들이 몇 가지 있다.

해쉬 테이블 충돌 해결 방법

 

위 그림처럼 키 값은 다르지만 Hash함수를 거치고 난 뒤의 해쉬 값이 동일하여 충돌이 발생하는 경우에는 데이터를 안전하게 저장하고 관리하기 위해서 충돌에 대한 해결을 해주어햐 하며 2가지가 존재한다. 

1. Separate Chaining 방식
   이 방법은 Linked List를 사용하는 방법이다. 인덱스에서는 데이터에 대한 참조 주소값만을 저장하고 충돌이 발생하는 인덱스의 경우 기존에 참조하고 있는 데이터에 충돌이 발생한 데이터를 연결 해주는 것이다. 
2. 
3. Open Addressing 방식
   이 방법은 Separate Chaining방식과는 다르게 추가적인 메모리를 사용하지 않고 기존에 정해진 Hash table의 배열값을 사용한다. 만약 충돌이 발생하게 된다면 충돌이 발생한 인덱스 다음 값을 참조하려 할 것이고, 이 값조차 비어있지 않다면 비어있는 공간을 찾기 위해서 계속해서 다음 번 인덱스 값을 참조 할 것이다.

 

해쉬 테이블 구현

구현 클래스 항목으로는 HashTable, Bucket, Node가 존재한다. 먼저 Node 클래스의 구현을 살펴 보자. 

 

class Node {
	public String key;
	public Object value;
	public Node afterNode;
	
	public Node(String key, Object value) {
		this.key = key;
		this.value = value;
	}
	
	public Node(Node afterNode) {
		this.afterNode = afterNode;
	}

	public Node getAfterNode() {
		return afterNode;
	}

	public void setAfterNode(Node afterNode) {
		this.afterNode = afterNode;
	}
}

Node클래스에서는 노드에 저장될 key와 value, 그리고 충돌에 의해서 해당 노드가 자신의 다음번 노드를 가르키기 위한 값을 관리한다. 그 외에는 별다른 로직이 들어가지는 않는다. 

다음으로는 Bucket에 대한 구현을 살펴 보자. Bucket 또한 데이터를 저장하는 용도로만 사용하는 클래스이기 때문에 상당히 간단하다. 

class Bucket {
	public String key;
	public Node node;
	
	public Bucket(String key, Node node) {
		this.key = key;
		this.node = node;
	}
}

 

이제 실제 HashTable의 삽입, 삭제, 가져오기가 구현된 HashTable클래스를 살펴보도록 하자.

class HashTable {
	//우리가 흔히 생각하는 HashTable의 크기. 여기서는 그냥 10만으로 ~
	private int hashSize = 100000;
	private Bucket[] buckets = null;
	
	public HashTable(int hashSize) {
		this.hashSize = hashSize;
		this.buckets = new Bucket[this.hashSize];
	}
	
	
	/**
	 * 삽입하는 메소드
	 * @param key
	 * @param value
	 */
	public void put(String key, Object value) {
		//1. hash Index값을 가져온다. 
		int hashIndex = hashFunction(key);
		//2. 해당 인덱스에 맞는 bucket을 가져온다. 
		Bucket bucket = buckets[hashIndex];
		//3. key와 value를 저장하는 node를 생성한다. 
		Node newNode = new Node(key, value);
		
		//4. 충돌 체크(충돌 안함) - bucket이 존재 하지 않으므
		if(bucket == null) {
			buckets[hashIndex] = new Bucket(key, newNode);
		} else { //5. 충돌 체크(충돌 함) - bucket이 존재하므로 
			Node curNode = bucket.node;
			Node curAfterNode = curNode.afterNode;
			//현재노드의 다음번 노드가 비어있으면 추가
			if(curAfterNode == null) {
				curAfterNode = new Node(key, value);
				curNode.afterNode = curAfterNode;
			} else { //현재의 노드의 다음번 노드가 존재하면 해당 노드로 
				//bucket이 가지고 있던 기본 노드값을 새 노드로 바꿔주고
				bucket.node = newNode;
				//바꿔준 노드 값에 현재의 노드를 달아준다. 
				bucket.node.afterNode = curNode;
			}
		}
	}
	
	/**
	 * 지우는 메소드
	 * @param key
	 */
	public boolean remove(String key) {
		boolean remove = false;
		//1. hash함수로 부터 hash인덱스를 가져와서
		int hashIndex = hashFunction(key);
		//2. 해당 인덱스의 bucket을 가져온다. 
		Bucket bucket = buckets[hashIndex];
		//3. bucket이 존재 한다면
		if(bucket != null) {
			//4. bucket의 노드를 가져와서
			Node node = bucket.node;
		 	
			String nodeKey = node.key;
			
			//5. 키가 존재 하고 afterNode가 존재하면 
			if(key.equals(nodeKey) && node.afterNode != null) {
				//5.1 bucket이 가르키는 노드에 afterNode로 바꿔서 저장한뒤.
				bucket.node = node.afterNode;
				//5.2 기존 노드는 null로 초기화 해서 없애 버린다.
				node = null; 
				remove = true;
			} else if(key.equals(nodeKey) && node.afterNode == null) { //6. 키가 존재하고 afterNode가 존재하지 않는다면,
				//6.1 bucket을 초기화 해버린다. 
				buckets[hashIndex] = null;
				node = null; //기존 노드만 null로 초기화 한다.
				remove = true;
			} else if(!key.equals(nodeKey)) { //7. 키가 존재 하지 않는데
				while(true) {
					//7.1 afterNode가 존재한다면
					if(node.afterNode != null) {
						Node afterNode = node.afterNode;
						String afterNodeKey = afterNode.key;
						//7.2 키값이 존재 하고 afterNode가 존재 한다면, 
						if(key.equals(afterNodeKey) && afterNode.afterNode != null) {
							//7.2.1 node의 afterNode값을 변환
							node.afterNode = afterNode.afterNode;
							afterNode = null;
							remove = true;
							//7.2.2 반복문 나간다.
							break;
						} else if(key.equals(afterNodeKey) && afterNode.afterNode == null) { //7.3 키 값이 존재하고 afterNode값이 존재하지 않는다면.
							//7.3.1 node의 afternode를 비워버린다. 
							node.afterNode = null;
							remove = true;
							//7.3.2 반복문 나간다.
							break;
						} else {
							node = afterNode;
						}
					} else {
						//afterNode가 존재하지 않는다면 루프 탈출
						break;
					}
				}
			}
		}
		
		return remove;
	}

	/**
	 * 값을 가져오는 메소드
	 * @param key
	 * @return
	 */
	public Object get(String key) {
		Object chooseValue = null;
		//1. hash함수로 부터 hash인덱스를 가져와서
		int hashIndex = hashFunction(key);
		//2. 해당 hash인덱스가 가르키는 버켓을 가져온다.
		Bucket bucket = buckets[hashIndex];
		//3. Bucket이 존재 한다면, 
		if(bucket != null) {
			//3. 버켓이 가르키는 노드를 가져온 뒤
			Node node = bucket.node;
			String nodeKey = node.key;
			//4. 유효성 검사를 한다.
			//5. 노드의 키와 전달 받은 키 값이 값다면 노드의 값을 곧바
			if(key.equals(nodeKey)) {
				chooseValue = node.value;
			} else { //6. 노드 키와 전달 받은 키가 다르다면 탐색을 시작하기 위한 반복문 진입.
				while(true) {
					//7. 현재 노드의 다음번 노드를 가져와
					node = node.afterNode;
					//8. 가져온 다음번 노드가 존재한다면
					if(node.afterNode != null) {
						//8-1. 키 값을 비교해서 같다면
						if(key.equals(node.key)) {
							//8-2. chooseValue에 저장하
							chooseValue = node.value;
							//8-3. 반복문을 나간다.
							break;
						} 
					} else { // 9. 가져온 다음번 노드가 존재안한다면 곧바로 반복문을 나간다. 
						break;
					}
					
				}
			}
		}
		
		return chooseValue;
	}
	
	/**
	 * Hash함수
	 * @param key
	 * @return
	 */
	private int hashFunction(String key) {
		char[] ch = key.toCharArray();
		
		int hash = 0;
		for(int i=0; i<ch.length; i++) {
			hash = hash + ch[i];
		}
		
		return hash;
	}
}

 

HashTable에 대한 소스 설명은 소스의 내용이 많아서 소스에 주석으로서 설명을 하였다.