안녕하세요. 가입인사후 처음 올리는 글이네요.
지금 학교에 들어와서 C를 처음 배우고 있는데요. 요즘 linked list에 대한 내용을 배우고 있습니다.
이번주 과제가
' 해시 테이블(hash table)을 linked list 와 rand 함수로 구현하는 방법에 대해 설명 하시오. '
인데요. 찾아 보니 해시 테이블은 자료구조 분야 라서 말이죠. 자료구조는 2학년때야 배우는데.
C 수업 시간에 나온 과제라 어쩌할지.... 지금 학교 도서관에서 자료구조론 책을 빌려오긴 했습니다만...
책보다는 사람이 설명해 주는게 이해가 빠른머리를 가지고 있어서....;;;;;
해시 테이블이 무엇이고 linked list와 랜덤 함수로 어떻게 구현하나요.
수 있는 녀석이죠. 자료구조 자체는 배열과 같습니다. 저장공간만 필요하죠. 중요한 것은 Hash 함수 입니다. 데이터를
이 함수를 통해서 저장공간의 위치를 계산하고 그 장소에 저장을 합니다. 검색할 때도 이 함수를 통해면 예상되는 장소를
찾을 수 있죠. 언제까지나 이론상입니다.
Hash라는 자료구조의 문제점은 저장공간의 충돌입니다. 다른 데이터를 해시 함수를 통해서 저장장소를 찾았는데 그
장소에 또 다른 데이터가 이미 있는 경우가 생깁니다. 이 문제의 해결 방법은 먼저 저장 공간을 늘리는 방법이 있지만 너무
많은 비용이 들어 갈 뿐아니라 근본적인 해결책인 충돌을 예방할 수 없죠. 그래서 다른 방법으로 같은 결과식의 장소를
늘려서 사용하는 경우가 있습니다. 이런 방법에 linked list가 사용될 수 있겠죠. 책에 이야기가 계속 될거라고 봅니다.
Hash table이라는 자료구조는 너무 이상적이라 쓸모 없어보이기도 하지만 범용이 아닌 특정 분야-특히 암호학-에서는
요긴하게 쓰여지고 있는 것으로 압니다.
과제에 대해서 한마디 하자면 rand와 Hash table은 별로 상관이 없어 보입니다. 대충 과목의 수준으로 이해하건데,
rand로 데이터를 생성한 뒤에 hash table에 저장하라, 단 저장공간의 충돌은 linked list를 통해서 방지하라 는 정도가
아닐까 싶군요.