MayBeMayBe

MayBeMayBe

Archive for the ‘Link’ Category

[Link] HASH TABLE

leave a comment »

 

 

Link

 

Hash Table

http://en.wikipedia.org/wiki/Hashtable

 

from wikipedia

A small phone book as a hash table.

Hash collision resolved by separate chaining.

 

Hash collision by separate chaining with head records in the bucket array.

 

Hash collision resolved by open addressing with linear probing (interval=1). Note that “Ted Baker” has a unique hash, but nevertheless collided with “Sandra Dee” which had previously collided with “John Smith”.

 

 

 

 

http://internet512.chonbuk.ac.kr/datastructure/hash/hash1.htm

링크참조.

 

부분발췌….

==============================================

Hashing Function

해싱 알고리즘을 해시 함수라고 부른다. 해싱 함수(hashing function) h(k)는 어떤 키 k에 대한 테이블 주소(table address)를 계산하기 위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다.

해싱은 빠른 속도의 데이터 검색 외에도, 전자서명을 암호화하고 복호화하는 데에도 사용된다. 전자서명은 해시 함수를 이용하여 변환된 다음, 해시 값(이를 요약 메시지라고 부른다)과 전자서명이 별도로 전송된다. 수신자는 송신자가 사용한 해시함수와 같은 것을 사용하여, 서명으로부터 요약 메시지를 뽑아내어 그것을 이미 수신한 요약 메시지와 비교한다. 그 비교 결과는 같아야만 전자서명이 유효한 것이다.

해시 함수는 원래의 값이나 키를 색인하는데 사용되며, 그 값이 관련된 데이터가 검색될 때마다 다시 사용된다. 그러나, 해싱은 항상 한 쪽 방향으로만 연산된다. 따라서, 해시된 값을 분석함으로써 해시 함수를 추출해내는 역방향 공학은 필요가 없다. 사실, 이상적인 해시함수는 그러한 분석에 의해 추론할 수 없어야 한다. 또한, 우수한 해시 함수는 서로 다른 두 개의 입력에 대해, 동일한 해시 값을 생산해서는 안된다. 만약 그렇게 되면, 충돌이 생긴다. 충돌 위험성이 매우 적은 해시 함수라야 훌륭한 해시 함수로 평가된다.

데이터베이스 저장이나 검색에 잘 적용되는 해시 함수는 오히려 암호화나 에러검출 목적으로는 잘 듣지 않을 수도 있다. 암호화에 사용되는 잘 알려진 해시 함수들이 몇 개 있다. 이러한 것들에는 전자서명을 요약 메시지라고 불리는 더 짧은 값으로 바꾸는 데 사용되는 요약 메시지 해시 함수 MD2, MD4, MD5 등과, 더 큰 요약 메시지 (60 비트)를 만드는 표준 알고리즘인 SHA (Secure Hash Algorithm) 등이 포함된다.

 

 

  • 레코드 키(key)들의 집합을 버켓(Bucket)주소의 집합에 대응시킨다는 의미에서 사상함수(mapping function)라고도 하며, 가장 이상적인 해싱 함수는 키 집합의 한 레코드(record)와 버켓 주소 집합의 한 레코드가 1 : 1 대응하여 해시 테이블의 정해진 범위에 고르게 분포되어 있어서 충돌을 최소화 하도록 하는 것인데 다음의 조건을 만족해야 한다.
    • 주소 계산이 빠르게 구해져야 한다.
    • 서로 다른 레코드의 계산된 값이 가급적 중복되지 않아야 한다.
  • 해싱 함수(Hashing function) –  레코드 키 값(k) → 해싱 함수 h(k)→ 해상표의 상대주소
  • 해시 테이블(hash table) –  레코드의 저장을 위한 자료구조로써 해상함수로부터 계산된 함수값에 해당하는 위치에 각 레코드를 한 개 이상 보관할 수 있는 버켓(bucket)들로 구성된 기억 공간이며, 주어진 key값을 가지고 해당 레코드를 빠르게 검색하기 위한 수단을 제공하며 레코드의 삽입과 삭제를 용이하게 한다.
  • 버켓(bucket) –  해싱함수에 의해 계산된 주소인 홈 주소(home address) 혹은 버켓 주소에 레코드 키를 저장하기 위해 마련된 기억장소를 말하며, 대개 한 개 또는 여러 개의 레코드를 저장할 수 있는 슬롯(slot)으로 구성된다.

 

 

Hashing Function, Bucket, Record

 

 

 

 

 

 

 

 

 

Written by MayBeMayBe

January 24, 2011 at 10:18

Posted in Link, Programming

[CriticalSection] Break Free of Code Deadlocks in Critical Sections Under Windows

leave a comment »

 

 

 

Break Free of Code Deadlocks in Critical Sections Under Windows

 

http://msdn.microsoft.com/en-us/magazine/cc164040.aspx

 

 

 

Critical Section Process Flow

 

struct RTL_CRITICAL_SECTION
{
    PRTL_CRITICAL_SECTION_DEBUG DebugInfo;
    LONG LockCount;
    LONG RecursionCount;
    HANDLE OwningThread;
    HANDLE LockSemaphore;
    ULONG_PTR SpinCount;
};

 

 

 

Written by MayBeMayBe

January 21, 2011 at 04:50

Posted in Link, Programming

[Link] C++ Under the Hood

leave a comment »

 

 

 

C++ Under the Hood

Jan Gray

March 1994

http://www.openrce.org/articles/files/jangrayhood.pdf

 

 

 

How a C++ compiler implements exception handling

By Vishal Kochhar

15 Apr 2002

http://www.codeproject.com/kb/cpp/exceptionhandler.aspx

 

 

 

Reversing Microsoft Visual C++ Part I: Exception Handling

igorsk

March 6 2006

http://www.openrce.org/articles/full_view/21

 

 

 

Reversing Microsoft Visual C++ Part II: Classes, Methods and RTTI

September 21 2006

http://www.openrce.org/articles/full_view/23

 

 

 

C++’s ‘virtual’ modifier

http://www.lrdev.com/lr/c/virtual.html

 

 

 

C++ Under the Hood

Scott Meyers, Ph.D.

May 2007

http://www.eetimes.com/EdTraining/DownloadFile?contentItemId=4126302&sponsor=embedded-systems-conference–esc-&isSurveySuccess=True

 

 

 

 

Written by MayBeMayBe

January 14, 2011 at 08:40

Posted in Link, Programming

Link – Economy

leave a comment »

Written by MayBeMayBe

August 28, 2010 at 05:40

Posted in Link

Link – IT

leave a comment »

 

Programming

 

Android Programming

 

====================================================================

 

에스티마

 

김국현의 낭만 IT

 

정지훈

 

광파리

 

Guru’s Blog

 

이찬진

 

조산구

 

혜민아빠

 

GrayNote

 

OOJOO

 

===================================================================

 

전자통신동향분석 – 한국전자통신연구원

 

KT경제경영연구소

 

 

 

 

Written by MayBeMayBe

August 28, 2010 at 03:22

Posted in Link