11/22/14

Hash Map - Theory & ANSI C Implementation.

What is Hash Map?

Hash Map is dictionary data structure.

Hash Map assigns values vn to keys kn from key set. Each of keys must be unique.

Hash Map has at minimum, following operations:
- search(kn) - returns vn assigned to kn,
- insert(kn, vn) - inserts (kn, vn) pair into hash map data structure properly, keeping association between key kn & value vn.
- delete(kn) - deletes (kn, vn) pair from hash map.

Often however, it also has following convenience operations:
- get_keys() - returns set of keys k1...km,
- size() - returns amount of elements in key set,
- perhaps more.


'Hash' part of 'Hash Map' name comes from 'hash function'.

Hash function usually helps (there's no guarantee for speed) to quickly find place where key is or should be located.


Implementation.

Key set can be implemented using array list of keys, with hash function we probably won't have to search through whole array list for a key.


(to be continued as soon as possible).

Source: [4], [19], [30], my partial education, my programming experience.

1 comment:

  1. hash_map ANSI C implementation has uses in:

    http://itsecinreal.blogspot.com/2014/08/nanite-war-computer-game.html

    theory will help to optimize code for speed & low memory usage.

    ReplyDelete