Quiz of Week 4 - Hash tables and Hash functions
이번 퀴즈는 굉장히 쉬워서 이해도가 떨어졌음에도 불구하고 다 맞을 수 있었다.
Hash Table과 Hash function에 대한 간단한 퀴즈의 조건이다.
1번 문제는 12개의 자릿수를 direct addressing활용할 때 key의 사이즈를 물어보고 있다.
2번은 h(x) = x mod 1000의 hash function과 hash table의 크기가 1000이며 최대 12개의 자리수를 사용할 때 최대 chain의 길이를 구하는 문제이다.
3번은 hash integer가 0~1000000의 범위 일 때 p(prime number)를 선택을 해야 한다.
마지막 문제는 hash function의 정수값이 -1000000~1000000의 범위일 때 universal family를 구축하는 방법에 대한 설명으로 옳은 것은에 대한 답을 찾는다.
1번 문제는 너무나 쉽게 L=12이므로 10^L 을 선택하면 된다.
2번은 12자리이므로 우선 10^12의 key를 가지고 hash function이 x mod 1000이므로 10^(12-3) = 10^9가 되겠다.
3번은 0~1000000범위에서 p는 1000000을 넘는 소수인 1000003이 되겠다.
마지막문제는 약간 헷갈릴 수 있지만 hash function의 universal family 범위가 0이 넘는 정수이기에 우선 1000000을 더해준 뒤 2000000을 초과하는 소수인 2000003을 p로 채택하면 universal family를 구축할 수 있다.
이번 퀴즈는 굉장히 쉬워서 이해도가 떨어졌음에도 불구하고 다 맞을 수 있었다.
Hash Table과 Hash function에 대한 간단한 퀴즈의 조건이다.
1번 문제는 12개의 자릿수를 direct addressing활용할 때 key의 사이즈를 물어보고 있다.
2번은 h(x) = x mod 1000의 hash function과 hash table의 크기가 1000이며 최대 12개의 자리수를 사용할 때 최대 chain의 길이를 구하는 문제이다.
3번은 hash integer가 0~1000000의 범위 일 때 p(prime number)를 선택을 해야 한다.
마지막 문제는 hash function의 정수값이 -1000000~1000000의 범위일 때 universal family를 구축하는 방법에 대한 설명으로 옳은 것은에 대한 답을 찾는다.
1번 문제는 너무나 쉽게 L=12이므로 10^L 을 선택하면 된다.
2번은 12자리이므로 우선 10^12의 key를 가지고 hash function이 x mod 1000이므로 10^(12-3) = 10^9가 되겠다.
3번은 0~1000000범위에서 p는 1000000을 넘는 소수인 1000003이 되겠다.
마지막문제는 약간 헷갈릴 수 있지만 hash function의 universal family 범위가 0이 넘는 정수이기에 우선 1000000을 더해준 뒤 2000000을 초과하는 소수인 2000003을 p로 채택하면 universal family를 구축할 수 있다.
댓글
댓글 쓰기