Hash Table

해시함수를 사용하여 키를 해시값으로 매핑하고,이 해시값을 index로
데이터의 값을 키와 함께 저장하는 자료구조.

해시함수(데이터의 키) > 해시 값(해시함수의 리턴값) >
해시값을 테이블의 인덱스 > 해당 인덱스에 값을 담는다.

HashTable 의 구성요소

key

고유한 데이터 값이며 해시함수의 input이 된다.다양한 길이의 값이 될수 있고,
이 상태로 최종 저장소(테이블)에 담게 되면 다양한 길이만큼 리소스를 잡아먹기때문에
해시함수를 통해 값을 축약하여 저장해야 공간 효율성을 추구할 수 있다.

Hash Function

키를 해시로 바꿔주는 함수이다.일정한 길이를 가진 테이블에 그 길이 내의 해시값(정수)으로 바꿔주어 저장소를 효율적으로 운용하도록 도와준다 .
그러나 문제는 아무리 정교하게 설계된 해쉬함수라도 다른 키값을 같은 해시값으로 만들어 동일한 저장 주소에 담게되는 충돌(Collison)이 일어나게 된다.
이러한 충돌을 최대한 적게 일어나게 만드는 것이 해시테이블에서 중요하다.

Hash

해시함수(key)의 결과물로 저장소에서 value와 매칭되어 저장된다.

Value

저장소에 최종적으로 저장되는 값으로 키-값으로 매칭되어 저장된다.

HashTable Method

insert= 주어진 키를 해시값으로 변환해 해당 해시값을 인덱스로 하는 자리에 값을 넣음
delete= 주어진 키를 해시값으로 변환해 해당 해시값을 인덱스로 하는 자리에 값을 삭제함
search= 위의 두 과정과 동일하게 값을 찾는다.

해시 테이블의 장점

해시 충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은
리소스로 많은 데이터를 효율적으로 관리할 수 있기때문
해시값을 인덱스로 사용함으로써 모든 데이터를 살피지 않아도
검색과 삽입,삭제를 빠르게 수행할 수 있다.

해시 테이블의 단점

• 순서가 있는 배열에는 어울리지 않는다.
  상하관계가 있거나, 순서가 중요한 데이터의 경우 순서에 상관없이 key만을 가지고 해시를 찾는 해시테이블에는 어울리지 않는다.

• 공간효율성이 떨어 진다.
  데이터가 저장되기전에 미리 공간을 확보해 놔야하기 때문에
  공간이 부족하거나 오히려 채워지지 않은 빈공간이 많이 남을 수 있다.

• 해시함수 의존도가 매우 높다
  평균 데이터 처리속도는 O(1)이지만,이는 해시함수의 연산을 고려하지 않은 결과이다.
  해시함수가 매우 복잡하다면 해시테이블의 모든 연산의 시간복잡도는 증가할 것이다.

linked list

링크드 리스트는 일렬로 연결된 데이터를 사용할때 사용하는 자료구조이다
이전 데이터가 다음 데이터의 주소를 가지고 있는 구조이다 .
배열같은 경우는 배열의 크기를 정한후 방의 크기를 줄이거나 늘릴수 없지만
링크드 리스트에선 이전 데이터에게 다음 데이터의 주소를 알려주기만 하면된다.

그러나 배열과 달리 데이터를 한번에 인덱스로 찾을 수 없고 첫번째 노드부터
찾는 노드가 나올때까지 노드를 거쳐거쳐 찾아야 한다.

linked list Property

Head: 첫번째 노드
Tail: 마지막 노드

linked list method

addToTail: 마지막에 새로운 노드를 추가
removeHead: 첫번째 노드를 삭제
contains: 리스트가 주어진 값을 가지고 있는지 탐색