해시 (Hash)

💡 Hash

연결 리스트에 비해 검색 & 추가 & 제거 & 수정의 시간복잡도 효율이 좋은 자료구조인 키 & 값 기반의 Hash

Hash -> Key & Value Array의 구조로 가정함

 

Hash의 메서드

• 시간복잡도를 효율적으로 바꿀 수 있는 메서드들
  • add()
  • remove(0
  • lookup() / find()
  • change()
• 시간복잡도가 최소 O(n)이 걸릴수 밖에 없는 메서드들
  • all entries
  • all keys
  • all values
• Hash에선 시간복잡도가 O(1)이지만 연결 리스트에선 O(n)이던 메서드들
  • size()
  • isEmpty()
  • isFull()
  • loadFactor()

 

Hash 함수 - hashCode()

• 해시 함수에 중요한것은 데이터의 속성이다
• 연산이 빨라야 한다
• 최대한 코드 충돌을 지양해야한다
• 코드를 재실행 했을떄 같은 객체라도 다른 값이 나올 수 있다
  • Objct의 hashCode()를 Override하지 않으면
    Object 클래스의 hashCode는 메모리 위치를 기반으로 실행되고
    재실행마다 객체는 다른 위치에 저장되기 때문에 다른값이 반환된다
• 같은 실행 환경일 경우두 요소가 같다면 같은 값을 반환해야 함
  
  • 객체의 경우 힙에서의 위치, 문자열의 경우는 문자열 비교 등