Java-자료구조 (Hash Table)

1. 해쉬 테이블

키(Key)에 데이터(Value)를 매핑할 수 있는 구조
해싱 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산
Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐
미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색을 지원한다.

2. 알아둘 용어

해쉬 함수(Hash Function): 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
- 해쉬(Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(hash Address): 해싱 함수를 통해 리턴된 고정된 길이의 값
해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
- 슬롯(Slot): 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간

3. 간단한 해쉬

3-1. hash table 클래스 만들기

* 참고 ( 객체 배열 )

객체 배열 선언시, 각 배열의 아이템은 각 객체를 참조할 수 있는 주소를 담을 수 있는 공간만 할당
- 각 아이템 생성시, 별도로 각 객체를 생성해줘야 함
- 즉, 객체 배열 선언시, 각 생성할 객체를 가리킬 주소만 저장할 공간을 배열로 만드는 것임

 public class main {
    public static void main(String[] args) {
        Students[] students = new Students[5];
 
        for(int i = 0; i < students.length; i++) {
            students[i] = new Student("00" + i, "홍길동" + i, "남자", (double)((int)(new Random().nextDouble() * 4.5 * 100)) / 100));
        }
        for(int i = 0; i < students.length; i++) {
            System.out.println("---------------");
            students[i].show();
        }
    }
}
 
// 이와같이 객체 배열을 만들 수 있다.

 // src/com.company.Hash/Hash.java
 
package com.company.Hash;
 
public class MyHash {
    public Slot[] hashTable;
 
    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }
 
    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }
}

3-2. 초간단 해쉬 함수를 만든다

Key가 문자열일 떄, 문자열의 앞 글자를 숫자로 변환해서, Division기법을 사용하여, Key에 대한 주소(인덱스 번호)계산
- Division 기법: 가장 간단한 해쉬 함수 중 하나로, 나누기를 통해, 나머지 값을 사용하는 방법

3-3. 해쉬 테이블 클래스에 해쉬 함수 추가

 // src/com.company.Hash/Hash.java
 
package com.company.Hash;
 
public class MyHash {
    public Slot[] hashTable;
 
    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }
 
    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }
 
    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
}

 public class Slot {
    String value;
    Slot(String value) {
        this.value = value;
    }
}
 
Slot[] hashTable = new Slot[20];
System.out.println(hashTable[0]);
// null

 public class Slot {
    String value;
    Slot(String value) {
        this.value = value;
    }
}
 
Slot[] hashTable = new Slot[20];
hashTable[0] = new Slot("test");
System.out.println(hashTable[0]);
System.out.println(hashTable[0].value);
 
// REPL.$JShell$40$Slot@5a20858a
// test

해시 테이블 클래스에 saveData()메서드 추가

 // src/com.company.Hash/Hash.java
 
package com.company.Hash;
 
public class MyHash {
    public Slot[] hashTable;
 
    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }
 
    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }
 
    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
 
    public boolean saveData(String key, String value) {
        Integer address = this.hashFunc(key);
        if(this.hashTable[address] != null) {
            this.hashTable[address].value = value;
        } else {
            this.hashTable[address] = new Slot(value);
        }
        return true;
    }
}

해쉬 테이블 클래스에 key에 대한 데이터를 가져오는 메서드 추가

 // src/com.company.Hash/Hash.java
 
package com.company.Hash;
 
public class MyHash {
    public Slot[] hashTable;
 
    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }
 
    // 내부 클래스
    public class Slot {
        String value;
        Slot(String value) {
            this.value = value;
        }
    }
 
    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
 
    public boolean saveData(String key, String value) {
        Integer address = this.hashFunc(key);
        if(this.hashTable[address] != null) {
            this.hashTable[address].value = value;
        } else {
            this.hashTable[address] = new Slot(value);
        }
        return true;
    }
 
    public String getData(String key) {
        Integer address = this.hashFunc(key);
        if(this.hashTable[address] != null) {
            return this.hashTable[address].value;
        } else {
            return null;
        }
    }
}

완성된 해시테이블 테스트

 // src/com.company/Main.java
 
package com.company;
 
import com.company.Hash.MyHash;
 
public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        System.out.println(mainObject.getData("HyunseoLee"));
    }
}
 
// 01044445555

4. 자료 구조 해쉬 테이블의 장단점과 주요 용도

장점
- 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다)
- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
단점
- 일반적으로 저장공간이 좀더 많이 필요하다
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요함
주요 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문)

5. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

기존 알고리즘의 문제점

 // src/com.company/Main.java
 
package com.company;
 
import com.company.Hash.MyHash;
 
public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        mainObject.saveData("David", "01066667777");
        mainObject.saveData("Dave", "01088889999");
        System.out.println(mainObject.getData("DaveLee"));
    }
}
 
// 01088889999

5-1. Chaining 기법

개방 해싱 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 방법

 // src/com.company.Hash/MyHash.java
 
package com.company.Hash;
 
public class MyHash {
    public Slot[] hashTable;
 
    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }
 
    // 내부 클래스
    public class Slot {
        public String key;
        public String value;
        public Slot next;
 
        public Slot(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
 
    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
 
    public boolean saveData(String key, String value) {
        // 해당 키에 대한 주소를 가져온다.
        Integer address = this.hashFunc(key);
 
        // 이미 해당 슬롯이 있다면
        if(this.hashTable[address] != null) {
            // linked list 기법을 사용해서 이어 붙여야 한다.
            // 일종의 해드라고 할 수 있다.
            Slot findSlot = this.hashTable[address];
            while(findSlot.next != null) {
                if(findSlot.key == key){
                    // 해당되는 키를 찾았다면 value만 바꿔주면 된다.
                    findSlot.value = value;
                    return true;
                } else {
                    findSlot = findSlot.next;
                }
            }
            // 만약 마지막까지 순회했다면
//            System.out.println("findSlot key >> " + findSlot.key);
//            System.out.println("findSlot value >> " + findSlot.value);
//            System.out.println("key >> " + key + " value >> " + value);
            findSlot.next = new Slot(key, value);
        } else {
            // 해당 슬롯에 아무것도 할당되어 있지 않다면
            this.hashTable[address] = new Slot(key, value);
        }
        return true;
    }
 
 
    public String getData(String key) {
//        System.out.println("we're just find >> " + key);
        Integer address = this.hashFunc(key);
        if(this.hashTable[address] != null) {
            Slot findSlot = this.hashTable[address];
            while(findSlot != null) {
//                System.out.println("Slot key >> " + findSlot.key);
//                System.out.println("Slot value >> " + findSlot.value);
                if(findSlot.key == key) {
                    return findSlot.value;
                } else {
                    findSlot = findSlot.next;
                }
            }
            return null;
        } else {
            return null;
        }
    }
}

 // src/com.company/Main.java
 
package com.company;
 
import com.company.Hash.MyHash;
 
public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        mainObject.saveData("David", "01066667777");
        mainObject.saveData("Dave", "01088889999");
        System.out.println(mainObject.getData("Dave"));
    }
}
 
// 01088889999

5-2. Linear Probing 기법

폐쇄 해싱 또는 Close Hashing 기법중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
- 저장공간 활용도를 높이기 위한 기법

 // src/com.company.Hash/MyHash.java
 
package com.company.Hash;
 
public class MyHash {
    public Slot[] hashTable;
 
    public MyHash(Integer size) {
        // object list
        this.hashTable = new Slot[size];
    }
 
    // 내부 클래스
    public class Slot {
        public String key;
        public String value;
        public Slot next;
 
        public Slot(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
 
    public int hashFunc(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length;
    }
 
 
    // Linear Probing 기법
    public boolean saveData(String key, String value) {
        // 해당 키에 대한 주소를 가져온다.
        Integer address = this.hashFunc(key);
 
        // 값이 있다면
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) {
                this.hashTable[address].value = value;
                return true;
            } else {
                // linear probing기법을 위해 address를 1더 해준다
                Integer currAddress = address + 1;
                while(this.hashTable[currAddress] != null) {
                    if(this.hashTable[currAddress].key == key) {
                        this.hashTable[currAddress].value = value;
                        return true;
                    } else {
                        currAddress++;
                        if(currAddress >= this.hashTable.length) {
                            return false;
                        }
                    }
                }
                this.hashTable[currAddress] = new Slot(key, value);
                return true;
            }
        } else {
            this.hashTable[address] = new Slot(key, value);
        }
        return true;
    }
 
 
    // Linear Probing 기법
    public String getData(String key) {
        Integer address = this.hashFunc(key);
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) {
                return this.hashTable[address].value;
            } else {
                Integer currAddress = address;
                while(this.hashTable[currAddress] != null) {
                    if(this.hashTable[currAddress].key == key) {
                        return this.hashTable[currAddress].value;
                    } else {
                        currAddress++;
                        if(currAddress >= this.hashTable.length) {
                            return null;
                        }
                    }
                }
                return null;
            }
        } else {
            return null;
        }
    }
}

 // src/com.company/Main.java
 
package com.company;
 
import com.company.Hash.MyHash;
 
public class Main {
    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee", "01022223333");
        mainObject.saveData("HyunseoLee", "01044445555");
        mainObject.saveData("David", "01066667777");
        mainObject.saveData("Dave", "01088889999");
        System.out.println(mainObject.getData("Dave"));
    }
}
 
// 01088889999

참고: JAVA HashMap

해쉬 테이블 구조를 활용하여 구현된 JAVA Collection Framework에 속한 클래스

 // src/com.company/Main.java
 
package com.company;
 
import com.company.Hash.MyHash;
 
import java.util.HashMap;
 
public class Main {
    public static void main(String[] args) {
 
 
        HashMap<Integer, String> map1 = new HashMap<>();
        map1.put(1, "사과");
        map1.put(2, "바나나");
        map1.put(3, "포도");
 
        HashMap<String, String> map2 = new HashMap<>();
        map2.put("DaveLee", "01033334444");
        map2.put("Dave", "01032221111");
        map2.put("David", "01044445555");
 
        System.out.println(map1.get(2));
        System.out.println(map2.get("Dave"));
    }
}
 
// 바나나
// 01032221111

7. 시간 복잡도

일반적인 경우(Collision이 없는 경우)는 O(1)
최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
Linear Probing, Chaining 기법 둘 다 동일

해쉬 테이블의 경우는 일반적인 경우를 기대하고 작성함

검색에서 해쉬 테이블의 사용 예

배열에 데이터를 저장하고, 검색할 때 O(n)
이상적인 해쉬 테이블 케이스에서 데이터를 검색할 때 O(1)

'Algorithm > Algorithm-Java' 카테고리의 다른 글

JAVA-자료구조 (Heap) (0)	2021.11.20
Java-자료구조 (Tree) (0)	2021.11.19
Java-자료구조 (시간 복잡도) (0)	2021.11.18
Java-자료구조 (Linked-List) (0)	2021.11.17
Java-자료구조 (Stack) (0)	2021.11.17

1. 해쉬 테이블
2. 알아둘 용어
3. 간단한 해쉬
4. 자료 구조 해쉬 테이블의 장단점과 주요 용도
5. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)
참고: JAVA HashMap
7. 시간 복잡도
검색에서 해쉬 테이블의 사용 예

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Java-자료구조 (Hash Table)

1. 해쉬 테이블

2. 알아둘 용어

3. 간단한 해쉬

3-1. hash table 클래스 만들기

3-2. 초간단 해쉬 함수를 만든다

3-3. 해쉬 테이블 클래스에 해쉬 함수 추가

4. 자료 구조 해쉬 테이블의 장단점과 주요 용도

5. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

5-1. Chaining 기법

5-2. Linear Probing 기법

참고: JAVA HashMap

7. 시간 복잡도

검색에서 해쉬 테이블의 사용 예

'Algorithm > Algorithm-Java' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

	public class main {
	public static void main(String[] args) {
	Students[] students = new Students[5];

	for(int i = 0; i < students.length; i++) {
	students[i] = new Student("00" + i, "홍길동" + i, "남자", (double)((int)(new Random().nextDouble() * 4.5 * 100)) / 100));
	}
	for(int i = 0; i < students.length; i++) {
	System.out.println("---------------");
	students[i].show();
	}
	}
	}

	// 이와같이 객체 배열을 만들 수 있다.

	// src/com.company.Hash/Hash.java

	package com.company.Hash;

	public class MyHash {
	public Slot[] hashTable;

	public MyHash(Integer size) {
	// object list
	this.hashTable = new Slot[size];
	}

	// 내부 클래스
	public class Slot {
	String value;
	Slot(String value) {
	this.value = value;
	}
	}
	}

	// src/com.company/Main.java

	package com.company;

	import com.company.Hash.MyHash;

	public class Main {
	public static void main(String[] args) {
	MyHash mainObject = new MyHash(20);
	mainObject.saveData("DaveLee", "01022223333");
	mainObject.saveData("HyunseoLee", "01044445555");
	System.out.println(mainObject.getData("HyunseoLee"));
	}
	}

	// 01044445555

	// src/com.company.Hash/MyHash.java

	package com.company.Hash;

	public class MyHash {
	public Slot[] hashTable;

	public MyHash(Integer size) {
	// object list
	this.hashTable = new Slot[size];
	}

	// 내부 클래스
	public class Slot {
	public String key;
	public String value;
	public Slot next;

	public Slot(String key, String value) {
	this.key = key;
	this.value = value;
	this.next = null;
	}
	}

	public int hashFunc(String key) {
	return (int)(key.charAt(0)) % this.hashTable.length;
	}

	public boolean saveData(String key, String value) {
	// 해당 키에 대한 주소를 가져온다.
	Integer address = this.hashFunc(key);

	// 이미 해당 슬롯이 있다면
	if(this.hashTable[address] != null) {
	// linked list 기법을 사용해서 이어 붙여야 한다.
	// 일종의 해드라고 할 수 있다.
	Slot findSlot = this.hashTable[address];
	while(findSlot.next != null) {
	if(findSlot.key == key){
	// 해당되는 키를 찾았다면 value만 바꿔주면 된다.
	findSlot.value = value;
	return true;
	} else {
	findSlot = findSlot.next;
	}
	}
	// 만약 마지막까지 순회했다면
	// System.out.println("findSlot key >> " + findSlot.key);
	// System.out.println("findSlot value >> " + findSlot.value);
	// System.out.println("key >> " + key + " value >> " + value);
	findSlot.next = new Slot(key, value);
	} else {
	// 해당 슬롯에 아무것도 할당되어 있지 않다면
	this.hashTable[address] = new Slot(key, value);
	}
	return true;
	}


	public String getData(String key) {
	// System.out.println("we're just find >> " + key);
	Integer address = this.hashFunc(key);
	if(this.hashTable[address] != null) {
	Slot findSlot = this.hashTable[address];
	while(findSlot != null) {
	// System.out.println("Slot key >> " + findSlot.key);
	// System.out.println("Slot value >> " + findSlot.value);
	if(findSlot.key == key) {
	return findSlot.value;
	} else {
	findSlot = findSlot.next;
	}
	}
	return null;
	} else {
	return null;
	}
	}
	}