자료구조2 [자료구조] 해쉬 테이블(Hash table) 자료구조 HashTable Key 값에 해싱된 Value를 저장하는 데이터 구조. Hash Hash는 일방향 함수이다. 어떤 동일한 값을 함수에 매개변수로 넘긴다면 정해진 하나의 해쉬 값을 도출한다. 하지만 그 역은 구할 수 없다. Hash 충돌 만약 해쉬 값을 Boolean 자료형으로 한다면 해쉬 값은 50%의 확률로 겹칠 것이다. 이러한 상황을 해쉬 충돌이라 한다. 완전한 해시 함수 어떤 hash 함수가 충돌없이 1:1대응을 할 수 있다면 이를 완전한 해시 함수라 한다. 충돌 극복 방법 1.Open Address 이 방법은 만일 해쉬 충돌이 생긴다면 그 다음 주소에 해당 값을 저장하는 방식으로 사용된다. 하지만 remove 기능을 효율적으로 구현하기 어려운 문제가 생긴다. 2.Separate Chai.. 2022. 7. 28. [Go] Slice와 Array 알고 쓰기 Slice C++의 Vector, Java의 ArrayList 등과 같이 사용할 수 있는 Go의 Slice. 코딩 테스트든 개발이든 가장 많이 사용하게 될 자료구조가 아닌 듯싶다. 그렇기에 Slice를 잘 사용하기 위해 기본적으로 알아야 하는 내용들의 이해를 돕기 위해 Array와 비교하여 요약하려 한다. Array와 Slice의 차이 기본적으로 Array는 memory에 동적으로 할당할 수 없다(정적인 자료구조). 생성 시에 크기를 지정해 주어야 하며 그에 맞춰 const 한 메모리를 할당하게 된다. 하지만 Slice는 그렇지 않다. Slice는 동적으로 할당할 수 있으며 크기를 따로 지정해 주지 않아도 된다(해도 됨). Array와 Slice 생성 방법 Array 몇 가지의 방법을 소개하겠다. 사실 .. 2021. 7. 21. 이전 1 다음
