해쉬

• Dynamic Set을 구현하는 효과적인 방법중 하나
  • 적절한 가정하에서 평균 탐색, 삽입, 삭제 시간 O(1)
  • 작업 속도를 빠르게 만들 수 있다.
  • Key value System을 이용해 자료를 정리
• 배열과 hashTable의 차이
  • 배열의 작업속도는 O(n)으로 비효율적
    • 순차적으로 검색하기 때문
  • HashTable의 작업속도는 O(1)
    • Key값만 호출하면 value가 반환되므로
• Hash Function
  • 개발자가 생성한 값의 크기에 따라 hashfunction이 인덱스에 담는다.
  • 만약 같은 크기의 값이 생성된다면 collision 즉, 해시 충돌이 일어나는데
    • 같은 인덱스에 또 다른 인덱스를 생성한다. 즉, 같은 인덱스의 2개의 쌍을 저장하는것이다.
      • 그러면 그 안에서 선형 검색이 이뤄진다.O(n) 결국 항상 상수 시간이 이뤄질 수는 없다.