TIL 정리_66

연결리스트는 수용량이 정해져 있지 않고, 스택과 큐를 사용하기위해 만들 수 있다
리스트 내에 무언가를 찾고 싶을때의 시간복잡도 O(n)이다 

-> 비효율적이다

리스트 내의 데이터를 조회할 때 유용한 데이터 구조를 사용해야 한다.

 

Hash : 해시

여러 상황에서 데이터를 빠르게 추가하거나 제거하도록 한 데이터 구조이다
또한 데이터를 빠르게 찾을 수 있는 자료구조가 해시이다
키와 값을 가지고 있으며 키가 주어지면 바로 연관된 값을 찾을 수 있다

Hash 메서드 
add() : 요소를 추가한다
remove() : 요소를 제거한다
lookup/find/contains : 어떠한 요소를 찾고자 할때 사용한다
change : 특정 요소를 수정하고 싶을 때 사용한다

엔트리를 불러오는 메서드 : all entries
모든 키와 값들을 불러오는 메서드 : all keys, all values

size, isEmpty, isFull 크기, 요소가 비었는지 채워져 있는지 확인하는 메서드
-> 보통 O(1)의 시간복잡도로 확인 가능하다

all entries, all keys, all values 
자료구조에서 n개를 불러오려면 무조건 n만큼 시간이 걸린다
//자료구조의 모든 것을 불러오는 메서드들은 시간복잡도를 바꿀 수 없다 

add(), remove() 등 : 시간 복잡도를 줄일 수 있다

 

 

해시 함수 

고려해야 할 사항

1. 데이터의 속성
->CSSC 아이디가 있을 때 아이디를 이 해시에 넣어야 해시 함수가 작동을 한다
-> CSSC 부분을 제거해야 한다

 

2. 해시 함수들은 빨라야 한다
-> 무엇이 주어지든 빠른 계산 결과를 내보내야 한다

 

3. 두 요소가 같다면 같은 값을 반환해야 한다
같다는 것의 의미는 여러가지이다
객체 : 힙에서의 위치에 따름(주소값)
문자열 : 글자를 한 개씩 비교

 

4. 동일한 실행 상황의 경우 항상 같은 값을 반환해야 한다

 

5. 코드를 새로 실행하면 객체가 같더라도 다른 값이 나올 수 있다

 

객체가 같더라도 다른 값이 나오는 이유 

 

Object 클래스에 hashCode가 속해있기 때문에, 데이터를 만들 때 덮어씌우게 된다
또한, 메모리 위치 기반으로 실행된다 
-> 객체의 hashCode 함수를 덮어씌우지 않으면 실행할 때마다 객체는 다른 위치에 저장되기 때문에 

다른 값이 반환된다

 

6. 이러한 고려사항을 기반으로 코드에서 최대한 충돌이 일어나지 않도록 주의해야 한다