데이터 구조 와 알고리즘 – 7. 해시 와 Hashtable 류

7.1. 해시 함수
산열 은 흔히 볼 수 있 는 데 이 터 를 저장 하 는 기술 로 이런 방식 에 따라 매우 신속하게 데 이 터 를 삽입 하고 되 찾 을 수 있다.해시 에 사용 되 는 데이터 구 조 는 산 목록 이 라 고 합 니 다.산 목록 은 빠 른 삽입, 삭제, 데 이 터 를 되 찾 는 작업 을 제공 하지만 최대 값 이나 최소 값 을 찾 는 등 검색 작업 을 수행 할 수 없습니다.이런 조작 에 있어 서 다른 데이터 구조 가 더욱 적합 할 것 이다.
 
7.2. 해시 함수 선택
배열 의 크기 를 선택 할 때 중요 한 원칙 은 소 수 를 선택 하 는 것 이다.
10007 은 소수 이 고 프로그램의 메모 리 를 낮 출 만큼 많은 메모 리 를 사용 하지 않 는 다.
다음 예 에서 해시 함수 Simple Hash 는 호 너 (Horner) 법칙 을 이용 하여 여러 가지 함 수 를 계산한다.

static void Main()
        {
            string[] names = new string[10007];
            string name;

            string[] somenames = new string[]
           { "David", "Jennifer", "Donnie","Mayo",
                "Raymond","Bernica","Mike", "Clayton","Beata","Michael"};

            int hashVal;

            for (int i = 0; i < 10; i++)
            {
                name = somenames[i];
                hashVal = SimpleHash(name, names);
                names[hashVal] = name;
            }
            ShowDistrib(names);
           
            Console.Read();
        }


        public static int SimpleHash(string s, string[]arr)
        {
           int tot = 0;
           char[] cname;
           cname = s.ToCharArray();
           for (int i = 0; i < cname.GetUpperBound(0); i++)
           {
               tot += 37 * tot + (int)cname[i];
           }
           tot = tot % arr.GetUpperBound(0);
           if (tot < 0)
           { tot += arr.GetUpperBound(0); }
           return (int)tot;
        }

        static void ShowDistrib(string[] arr)
        {
           for (int i = 0; i < arr.GetUpperBound(0); i++)
           {
               if (arr[i] != null)
               { Console.WriteLine(i+" "+arr[i]); }
           }
        }

 
7.3. 산 목록 의 데 이 터 를 찾 습 니 다.
산 목록 에서 데 이 터 를 찾 으 려 면 키 의 산 열 값 을 계산 한 다음 배열 에 대응 하 는 요 소 를 방문 해 야 합 니 다.이런 검색 방식 은 하나하나 찾 는 것 보다 훨씬 효율 적 이다.
 
7.4. 충돌 해결
7.4.1 통 식 산열 법
통 은 산열 표 요소 에 저 장 된 간단 한 데이터 구조 로 여러 개의 데이터 항목 을 저장 할 수 있다.대부분의 실현 에서 이러한 데이터 구 조 는 하나의 배열 이다. 예 를 들 어 Array List 류 이다.
통식 산열 법 은 최종 적 으로 필요 한 것 은 사용 하 는 배열 의 수량 을 최대한 적 게 유지 하 는 것 이다.
데이터 항목 삽입
해시 함수 로 데이터 항목 을 저장 할 배열 (해시 키) 을 확인 한 다음 이 데이터 항목 이 배열 안에 있 는 지 확인 합 니 다.존재 한다 면 하지 않 는 다.존재 하지 않 으 면 이 배열 에 데이터 항목 을 추가 합 니 다.
데이터 항목 이동
해시 함수 로 데이터 항목 을 어떤 배열 (해시 키) 로 옮 겼 는 지 확인 한 다음 이 데이터 항목 이 배열 안에 있 는 지 확인 합 니 다.존재 하면 데이터 항목 을 옮 깁 니 다.존재 하지 않 으 면 하지 않 는 다.
7.4.2 개방 주소 법
주소 지정 함 수 를 열 면 해시 표 배열 에서 빈 셀 을 찾 아 데이터 항목 을 방지 합 니 다.
두 가지 서로 다른 오픈 주소 정책:
선형 탐사
삽입 하려 는 배열 단원 을 선형 함수 로 확인 합 니 다.빈 단원 을 찾 을 때 까지 순서대로 시도 합 니 다.
문제 가 발생 할 수 있 는 것 은 배열 내 인접 단원 중의 데이터 요소 가 집합 으로 가 까 워 지면 서 후속 빈 단원 의 탐색 시간 이 길 어 지고 효율 이 낮 아진 다 는 것 이다.
제곱 탐사
제곱 함 수 는 어떤 단원 을 시도 해 야 하 는 지 확인 합 니 다.
제곱 탐사 법의 재 미 있 는 속성 은 산열 표 의 나머지 단원 이 절반 보다 적은 상황 에서 항상 빈 단원 을 찾 을 수 있다 는 것 이다.
7.4.3 이중 산열 법
두 가지 조건: 해시 함 수 는 0 까지 계산 해 서 는 안 됩 니 다.시계의 크기 는 반드시 소수 여야 한다
 
7.5.5 Hashtable 클래스
초기 용량 을 가 진 산 목록 을 예화 하거나 기본 용량 을 사용 할 수 있 습 니 다.물론 초기 용량 과 초기 부하 계 수 를 동시에 지정 할 수 있다.

            Hashtable symbols = new Hashtable();
            Hashtable symbols = new Hashtable(50);
            HashTable symbols = new Hashtable(25, 3.0F);

 
7.5.1. 산 목록 에서 키워드 와 수 치 를 각각 되 찾 습 니 다.
Hashtable 클래스 는 산 목록 에서 키워드 와 수 치 를 되 찾 는 데 매우 유용 한 두 가지 방법 이 있 습 니 다. 즉, Keys 와 Values 입 니 다.이 방법 들 은 Enumerator 대상 을 만 들 었 습 니 다. For Each 순환 이나 다른 기술 로 키워드 와 수 치 를 검사 할 수 있 습 니 다.

Hashtable symbols = new Hashtable(25);
            symbols.Add("salary", 100000);
            symbols.Add("name", "David Durr");
            symbols.Add("age", 45);
            symbols.Add("dept", "Information Technology");
            symbols["sex"] = "Male";
            Console.WriteLine("The keys are: ");
            foreach (Object key in symbols.Keys)
                Console.WriteLine(key);
            Console.WriteLine();
            Console.WriteLine("The values are: ");
            foreach (Object value in symbols.Values)
                Console.WriteLine(value);

 
7.5.2. Hashtable 류 의 응용 프로그램: 컴퓨터 용어 표
산 목록 의 흔 한 응용 중 하 나 는 바로 용어 표 나 용어 사전 을 구성 하 는 것 이다.이 소절 은 산 목록 을 사용 하 는 방법 중 하 나 를 예 로 들 어 설명 할 것 이다. 즉, 컴퓨터 용어 표 이다.프로그램 은 먼저 텍스트 파일 에서 일련의 용어 와 정 의 를 읽 습 니 다.이 과정 은 서브루틴 BuildGlossary 에서 인 코딩 되 어 이 루어 집 니 다.텍스트 파일 의 구 조 는 단어, 정의, 쉼표 로 단어 와 정의 사 이 를 구분 하 는 것 입 니 다.이 용어 표 의 모든 단 어 는 하나의 단어 이지 만 용어 표 도 처리 단 어 를 쉽게 바 꿀 수 있다.이것 이 바로 쉼표 로 구분 자 를 만 들 지 않 는 이유 다.또한, 이러한 구 조 는 단 어 를 키워드 로 사용 할 수 있 으 며, 이것 은 이 산 목록 을 구성 하 는 정확 한 방법 이다.다른 서브루틴 DisplayWords 는 단 어 를 목록 상자 에 표시 하기 때문에 사용 자 는 단 어 를 선택 하여 정 의 를 얻 을 수 있 습 니 다.단어 가 키워드 인 만큼 산 목록 에서 단 어 를 되 돌려 주 는 키스 방법 을 사용 할 수 있다.그리고 사용 자 는 정 의 된 단 어 를 볼 수 있 습 니 다.

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        private Hashtable glossary = new Hashtable();

        private void Form1_Load(object sender, EventArgs e)
        {
            BuildGlossary(glossary);
            DisplayWords(glossary);
        }

        private void BuildGlossary(Hashtable g)
        {
            StreamReader inFile;
            string line;
            string[] words;
            inFile = File.OpenText(@"c:\111.txt");
            char[] delimiter = new char[] { ',' };
            while (inFile.Peek() != -1)
            {
                line = inFile.ReadLine();
                words = line.Split(delimiter);
                g.Add(words[0], words[1]);
            }
            inFile.Close();
        }
        private void DisplayWords(Hashtable g)
        {
            Object[] words = new Object[100];
            g.Keys.CopyTo(words, 0);
            for (int i = 0; i <= words.GetUpperBound(0); i++)
                if (!(words[i] == null))
                    lstWords.Items.Add((words[i]));
        }

        private void lstWords_SelectedIndexChanged(object sender, EventArgs e)
        {
            Object word;
            word = lstWords.SelectedItem;
            txtDefinition.Text = glossary[word].ToString();
        }
    }
}