해시테이블_개선

1. 해시테이블 구조 개선

완벽한 해시함수는 없어서 언젠가는 충돌한다->충돌해소방법 필요

->일반적으로는 내부구조차원에서 충돌처리

(내부구조 변경 안하고 충덜처리가 더 좋다!)

1) Linked overflow : 해시테이블의 각 칸은 연결리스트이다.

Linked overflow 테이블에 항목을 삽입.

테이블은 크기가 10이고, 해시함수는 나머지 연산일 때 다음의 플레이어를 테이블에 삽입한다.

player1: 345,752

player2: 546,182

player3: 798,500

player4: 123,430

->나머지연산적용(해시함수적용): 2, 2, 0, 0

player3,4

player1,2

0                                                                                                                        9

!-> 이 방법을 사용하면 충돌을 전혀 걱정할 필요가 없다.

해시들이 충돌한다고 해도, 나중 자료가 목록의 끝에 추가될 뿐 문제는 없다.

2) 키 검색

해시함수가 효율적이며 충돌이 많이 일어나지않는다면, 해시테이블에서 어떤 항목을 거의

순식간에 찾을 수 잇다.

Linked overflow 해시테이블에서 특정항목을 찾는과정

1. 항목을 해시해서 색인을 얻는다.

2. 그 색인에 해당하는 칸의 연결리스트에서 그 항목을 찾는다 ->다른칸을 볼필요 없다!

그 칸의 연결리스트에서 해당 항목을 찾으려면 선형적인 검색이 필요하지만, 

목록의 길이가 그리 크지 않다면 매우 빠르게 결과를 얻을 수 있다.

테이블에 해당 항목이 없다고 해도, 마찬가지로 칸 하나의 목록하나만 훑으면 항목이 없다는

사실을 알 수 있다.

!-> 훨씬 효율적!

Add 지정한 키와 값을 가지는 요소를 Hashtable 에 추가.

Remove Hashtable 에서 지정한 키를 가지는 요소를 제거

ex)

namespace HashEX
{
    public class FileFormatTable
    {
        private hashtable openWith;
        public FileFormatTable();
        {
            openWith = new Hashtable;
            //추가
            openWith.Add ("bmp", "paint.exe");
            openWith.Add ("txt", "notepad.exe");
            openWith.Add ("dib", "paint.exe");
            //이미 할당된 키일 경우
            try{ openWith.Add("txt", "winword.exe"); 
            catch{ Console.WriteLine("An elementary with key = \"txt\" already exists");
 
            //제거
            openWith.Remove("dib");
        }
        public void printTable(){
            //탐색
            foreach(DictionaryEntry d in openWith){
                Console.WriteLine("Key = {0}, value={1}", d.Key, d.Value);
            }
        }
    class Main
    {
        public static void Main(string[] args)
        {
            FileFormatTable fileFormatTable = new FileFormatTable();
            fileFormatTable.printTable();
        }
    }
}
 
Colored by Color Scripter 
cs 
 
 
 2016.10.18. 19:40