[2023-08-01] Intro to Database Systems 7강 - Hash Tables

[CoodingPenguin]

📌 개요

• 시간: 2023-08-01(화) 21:00
• 자료: 7강 Hash Tables
• 참여자: 펭귄, 그루트, 렉사, 나강

✍️ 준비

아래 양식을 복사해 스터디 준비를 완료해주세요!

## 💬 생각

<!--강의를 듣고 생각한 내용을 3줄 내로 간단히 정리해주세요!-->

- ...

## ❓ 질문

<!--공부하면서 궁금한 점을 작성해주세요!-->

- ...

## 📚 참고 자료

<!--공부하면서 같이 공부한 자료를 첨부 및 공유해주세요!-->

- [...](...)

[jonyejin]

💬 생각

1.

Q: 해시 함수를 언제 쓰는게 좋을까?
A: 나같은 경우에는, 최근에 크롤링 한 70GB정도에서 중복성을 검사할 일이 있었는데
각각 10KB~1MB밖에 안되는 문서여서 굉장히 개수가 많았기 때문에
pair을 만들어서 비교하기에는 시간복잡도가 너무 높았다.

이때 해시 함수를 만들어서 전체 문서를 10개정도의 통에 나눠 담은 후,
그 통 내에서만 pair을 만들어서 비교했더니 시간복잡도가 훨씬 줄어든 경험이 있었다.

2.

해시함수의 의의: key가 O(1)만에 index가 될 수 있다?

🌟 내용 정리

• 어떤 해시 함수를 쓰는게 좋은지
  • Facebook XXHash가 Sota이다.
  • CRC도 네트워크 시간에 배운 기억이 있음!
  • 해시 함수의 benchmark는 bit/sec이다.
• Static Hashing Schemes
  1. Linear Probe Hashing
     - 이미 그 키가 차있으면 다음 빈칸에다가 미루어서 저장한다.
     - 찾을 때 굉장히 곤란해짐, 중간중간 몇개를 삭제한 이후이면 더 곤란해짐.
     - 링크드 리스트 방식이 훨씬 낫지 않아?
  2. Robin Hood Hashing
     • Cuckoo Hashing
• Dynamic Hashing Schemes

📚 참고 자료

• [Database] DBA급 개발자로 - #6 Hash Table | DEVVY

[Nagunt]

💬 생각

• DBMS에서 사용하는 데이터 구조 중 Hash Table에 관한 강의. Hash function은 Facebook XXHash가 좋대요.
  • 크기가 고정되어 있는 static hash table
    • linear prove hashing, robin hood hashing, cuckoo hashing
  • 크기가 확장될 수 있는 dynamic hash table
    • chained hashing, extendible hashing, linear hashing
• 속도와 확장성은 trade-off 관계, 요즘은 B+ tree를 많이 쓴다네?

❓ 질문

• hash table은 키가 반드시 unique해야 하는 걸로 알고 있었는데 non-unique key를 다루는 것은 데이터베이스에서 사용하기 때문인걸까?
  • 대충 예외 처리 정도로?

📚 참고 자료

• [데이터베이스] Linear Hashing(선형 해싱) | jeongstudy
• [Database] DBA급 개발자로 - #6 Hash Table | DEVVY

[IamGroooooot]

💬 생각

컴공 공부하면서 배운 내용이 대부분이라서 어렵지 않았다.
쿠쿠해싱은 처음 봤는데 천재인듯..
멀티 쓰레드에서는 어떤 고민 사항이 있는지 궁금하다.
DB에서는 성능보다 일관적인 안정성을 중요시한다는 것이 기억에 남는다.

[CoodingPenguin]

💬 생각

• ...

❓ 질문

• ...

📚 참고 자료

• ...