EminentStar's Dev Wiki

기초지식키들의 전체 집합을 U라고 했을 때, 실제로 저장되는 키들의 집합은 K라고 하고 이 K는 U에 비해 상대적으로 작다. 실제 저장되는 K집합이 U에 비해 상대적으로 작기 때문에 해시테이블 T를 위해서 할당된 대부분의 공간이 낭비될 수 있다. 그래서 이렇게 사전에 저장된 키들의 집합 K가 모든 가능한 키들의 전체 집합 U에 비해 훨씬 작을 때 해시 테이블은 직접 주소 테이블보다 훨씬 작은 공간을 필요로 한다. 이때 해시 테이블의 크기를 m이라고 하고 일반적으로 |U|보다 훨씬 작다. 해싱을 이용한 방법에서는 키 k를 갖는 원소는 위치h(k)에 저장된다. 즉 키로부터 저장될 위치를 계산하기 위해 해시 함수 h를 사용한다. 여기서 h는 키들의 전체 집합 U를 해시 테이블 T[0..m-1]의 각 위치에 대..

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 알고리즘이다.== 해시 함수는 주로 3가지의 목적으로 사용된다.Fast Table LookupMessage digestsEncryption Fast Table LookupFast table lookup은 해시 함수와 해시테이블을 사용해서 구현될 수 있다. 해시 테이블을 사용하는 경우 빠른 삽입, 삭제 및 조회 요소는 우선순위다. 이론적으로, 삽입, 삭제, 조회(lookup) 를 동시에 수행할 수 있다. 자, 어쨌든 해시 테이블은 무엇인가? 부가설명해시 테이블은 배열인데, 해시 함수와 커플링 된 함수다. 해시 함수는 데이터를 인풋으로 가지는데 우리는 이것을 키라고 부른다. 그리고 해시 함수의 아웃풋은 해시값이라고 부른다. 해시값은 인풋 키..

연결리스트는 동적인 데이터를 처리하는 것과 관련된 수많은 문제의 근간을 이루는 자료 구조이다. 연결리스트의 종류Singly Linked ListDoubly Linked ListCircular Linked List Singly Linked List리스트의 다음 원소에 대한 연결고리가 들어있다.리스트의 마지막 원소는 꼬리라고 부르며, 연결고리는 비워두거나 null로 지정한다. 앞으로만 Traversal할 수 있다. So, 리스트를 완전 종주하려면 항상 첫 번째 원소부터 시작해야 한다.So to speak, 리스트에 있는 모든 원소의 위치를 파악할 때 리스트의 첫 번째 원소에 대한 포인터나 레퍼런스가 있어야만 한다. 그포인터나 레퍼런스는 보통 별도의 자료구조에 저장한다. Doubly Linked List이중 ..