집합과 맵(Hash)

해시(Hash)

• 해시는 단방향 암호화 기법인 해시함수를 이용하여 생성된 고정된 길이의 비트열을 의미한다.
  (복호화 불가능)
• 해시 함수는 입력된 임의의 데이터를 고정된 길이의 데이터 변경하여 출력해준다.
  • 키: 원본 데이터
  • 해시값(Hash Value): 해싱 후 데이터
  • 해싱: 키 -> 값 변환 과정
• 해시 충돌(Hash Collision): 변환이 이루어진 후 변환된 값이 중복되는 경우 발생 가능
  • 해결법
    • 체이닝(Chaining)
    • 개방 주소법(Open Addressing)
    • Linear Probing
    • Quadratic Probing
    • Double Hashing

      ---

HashTable, HashMap

• 해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

• 추가, 삭제, 검색에서 O(1)의 시간 소요

C#에서의 해시테이블 (.NET)

• Hashtable 클래스
  • Non-generic
  • 박싱/언박싱 지원
  • Double Hasing 방식

Hashtable ht = new Hashtable();
ht.Add("집","집에가고싶다");
ht.Add("학원","학원가기싫다");

if(ht.Contains("집"))
{
	Console.WriteLine(ht["집"]);
}

• Dictionary<TKey, TValue> 클래스
  • Generic
  • Key, Value값 모두 Strong type
  • 박싱/언박싱 X
  • Chainig 방식

Dictionary<int, string> bDay = new Dictionary<int, string>();
bDay.Add(411, "내생일");
bDay.Add(410, "쨌든 누구 생일");

string name = bDay[0];
Console.WriteLine(name);

• ConcurrentDictionary<TKey,TValue> 클래스
  • 멀티쓰레딩 환경에서 Dictionary를 간편하게 사용 가능(.NET 4.0~)
  • 추가: TryAdd()
  • 검색: TryGetValue()
  • 갱신: TryUpdate()
  • 삭제: TryRemove()

using System;
using System.Collections;
using System.Collections.Concurrent; // ConcurrentDictionary
using System.Threading;
using System.Threading.Tasks;

namespace ConcurrentApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var dict = new ConcurrentDictionary<int, string>();

            Task t1 = Task.Factory.StartNew(() =>
            {
                int key = 1;                
                while (key <= 100)
                {
                    if (dict.TryAdd(key, "D" + key))
                    {
                        key++;
                    }
                    Thread.Sleep(100);
                }
            });

            Task t2 = Task.Factory.StartNew(() =>
            {
                int key = 1;
                string val;
                while (key <= 100)
                {
                    if (dict.TryGetValue(key, out val))
                    {
                        Console.WriteLine("{0},{1}", key, val);
                        key++;
                    }
                    Thread.Sleep(100);
                }
            });

            Task.WaitAll(t1, t2);
        }
    }
}

참고1, 참고2