array와 Hash Table의 차이점
array: 시간 복잡도가 O(n)임.
Hash Table: 시간 복잡도가 O(1)임.
array의 원리
array 내의 모든 값들을 비교한다. 따라서 시간 복잡도가 O(n)이다.
Hash Table의 원리
찾고자하는 단어가(key) Hash Function을 통과하면 특정 숫자로 변환된다.
변환된 숫자를 테이블에서 가져오기만 하면 되기 때문에 시간 복잡도가 O(1)이다.
예를 들어 big이라는 단어가 Hash Fuction을 통과해 3이라는 숫자가 나왔다고 하자. 그럼 table에서 세번째에 해당하는 value를 가져오기만 하면 된다. 즉, array처럼 모든 값을 비교할 필요가 없다는 뜻이다.
