TA#0 Abstract Notes(II)
Updated: Apr 6, 2021
#TechnicalArtist #Interview #GameEngine #Programming
This blog writes about some frequently asked interview questions for Technical Artists(TA). TAs, as the bridge between artists and programmers, are required to cover range of knowledge including programming, art, design, color, game engines, physics, algorithm... whatever.
The topic in this note is Data Structure and Algorithm.
I. Hash Table.
In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values.
-- Wikipedia description.
Initial reason for having a hash table / hash map to store information is also for the sake of efficiency. Say if we store the key-value pairs in a linked list, and we want to lookup the key in the whole list, it could be expensive, at least O(n), not even considering the complexity of comparing query key with the element key.
The principle of using hash table to lookup is that we implement a hash function, which takes the key as input and outputs an integer. This integer is the index of the "bucket" where the key will be placed in the hash map. Generally we won't promise that there are exactly one key in each bucket. Namely this is saying the bucket index and the key is not 1-to-1. It is (highly) possible that there are some collisions. Formally, for key A and key B, Pr(h(A) == h(B)) ≠ 0 in general case. We do want to lower down this probability, or specifically we want to lower the chance of putting to many eggs in a single bucket, otherwise the hash table will be equivalent as a linked list in lookup.
Some important hash function related definitions:
Load factor = n/k, n is the # of entries in the hash table, while k is the # of buckets. As load factor becomes bigger, the hash table is slower.
Perfect hash function, hash functions that have no collisions.
Some resolutions for collisions:
Open address with probes. This is saying if the bucket where the key should be hashed to is occupied, the key is then redirected to some other buckets. The way to decide its next destination may due to different implementation.
Separate Chaining. Each bucket is itself another data structure (a linked list, a sequence, or even another hash map).
II. Doubly Linked List.
The doubly linked list is a linked list where its nodes also know which node the precursor is. i.e. for a node c, both c.next and c.prev is recorded.
This allows O(1) insert and delete.