Hash 구현해보기 Java

해시란 키에 해당하는 고유한 숫자 값을 통해 해당하는 값(value)으로 바로 찾아갈 수 있는 O(1)의 복잡도를 띄는

 

굉장히 빠른 알고리즘이다.  자바에서는 HashMap <k, v> 이 예이다.

 

https://stackoverflow.com/questions/3069709/what-is-a-hash-function-in-java

What is a hash function in java?

하지만 동일한 고유 숫자 값에의한 충돌이 나는 경우에는 충돌을 처리해주어야 하는데 대표적으로 linear 방식과

 

chaining 방식이 있다.

 

구현한 해시는 chaning 방식을 통해서 충돌을 해결하는 간단한 해시 자료구조이다.

 

키인 firstName을 통해 사원을 저장 삭제 조회할 수 있는 해쉬이다.

 

 

// hashtable은 연결 리스트로 구현하여 해쉬시 체이닝이 되도록 구현하였다.

 

	class chained_hash_table {
	LinkedList<StoredEmployee>[] hashtable;
	public chained_hash_table() {
	hashtable = new LinkedList[100];
	for(int i=0; i<hashtable.length; ++i) {
	hashtable[i] = new LinkedList<StoredEmployee>();
	}
	}
	//넣거나
	public void put(String key, Employee employee){
	int hashedkey = hashKey(key);
	hashtable[hashedkey].add(new StoredEmployee(key,employee));
	}
	//조회
	public Employee get(String key) {
	int hashedKey = hashKey(key);
	ListIterator<StoredEmployee> iterator = hashtable[hashedKey].listIterator();
	StoredEmployee storedEmployee;
	while(iterator.hasNext()) {
	storedEmployee = iterator.next();
	if(storedEmployee.key.equals(key)) {
	return storedEmployee.employee;
	}
	}
	return null;
	}
	//빼거나
	public Employee remove(String key) {
	int hashedKey = hashKey(key);
	ListIterator<StoredEmployee> iterator = hashtable[hashedKey].listIterator();
	int idx = -1;
	StoredEmployee storedEmployee = null;
	while(iterator.hasNext()) {
	storedEmployee = iterator.next();
	idx += 1;
	if(storedEmployee.key.equals(key)) {
	break;
	}
	}
	if(storedEmployee == null || storedEmployee.key.equals(key)) {
	return null;
	}
	else {
	hashtable[hashedKey].remove(idx);
	return storedEmployee.employee;
	}
	}
	public
	void printHashTable() {
	for(int i=0; i< hashtable.length; ++i) {
	if(hashtable[i].isEmpty()) {
	System.out.println("Position" + i + ": empty");
	}
	else {
	System.out.println("Posiition" + i +": ");
	ListIterator<StoredEmployee> listIterator = hashtable[i].listIterator();
	while(listIterator.hasNext()) {
	System.out.print(listIterator.next().employee);
	System.out.println("->");
	}
	System.out.println("null");
	}
	}
	}
	private int hashKey(String key) {
	return key.hashCode() % hashtable.length;
	}
	}

view raw .java hosted with ❤ by GitHub

 

// StoredEmployee

// 해당 키값과 Employee를 쌍으로 가지는 클래스

 

	class StoredEmployee {
	public Employee employee;
	public String key;
	public StoredEmployee(String key, Employee employee) {
	this.employee = employee;
	this.key = key;
	}
	public Employee getEmployee() {
	return employee;
	}
	public String getKey() {
	return key;
	}
	}

view raw .java hosted with ❤ by GitHub

// Employee 클래스

 

 

	class Employee
	{
	String firstName;
	String lastName;
	int Id;
	public Employee(String firstName, String lastName, int id) {
	this.firstName = firstName;
	this.lastName = lastName;
	Id = id;
	}
	}

view raw .java hosted with ❤ by GitHub