Matlab hashtable

Structs in Matlab are very usefull for collecting associated data together. However in Matlab you are limited to using valid Matlab variable names for the fields in the struct, even when using dynamic indexing.

For example.

>> h.('bad name') = 10
??? Invalid field name: 'bad name'.

What matlab requires is a hashtable object, sometimes refered to as a dictionary in other programming language. A hashtable can associate any string (key) with a value and retrieve the value later. More generic hashtables allow keys to be arbitrary objects but for the sake of simplicity I stick to strings for this implementation.

First of all download the hashtable object

Now you can try the following

   h = hashtable
   h.x = 10;
   y = h.x;

That was just like a standard matlab struct but it has other tricks.

h   = hashtable
h.x = 10;
y   = h;
h.x = 20;
y.x

  ans =

     20

Thats right, hashtable is a reference object. Assigning the hashtable instance to another variable does not make a copy of the data.

Lets try to use non standard field names.

h = hashtable
h.('a funny key') = 10;
y = h.('a funny key')

y =

    10

How does all this work?

First of all I am using a combination of nested functions and standard Matlab OOPs objects. The M-OOPS give me the ability to overide subsref and subsasgn to get the funky indexing and the nested functions give me the reference object behaviour.

The storage is managed by generated a hash of the string and using that hash to index into a storage cell array. My hash generating function is

function hash = hashcode(str)
    str = uint32(str(:))';
    hash = uint32(5381);
    for c = str
        hash = bitshift(hash, 5) + hash + c;
    end
end

I have a C version of the above function but for portability it is easier to use pure Matlab code. Unfortunately the pure M code is about 10 times slower in generating the code.

Once we have the code we generate a number over the number of storge buckets we have available.

 function i = hash(string)
      i = rem(hashcode(string),buckets) + 1;
 end

Retrieving the value is fairly simple. The modified hash is used to retrieve a structure array from a cell array of buckets. Generally the structure array is empty or contains only a few key-value pairs. A linear search is performed on the structure array to get the correct value.

   function out = get(key)
      i = hash(key);
      if isempty(contents{i})
         out = [];
         return;
      end
      items = contents{i};
      for j = 1:length(items);item = items(j);
         if isequal(item.key, key)
            out = item.value;
            return;
         end
      end
      out = [];
      return;
   end

Putting is more complex. We wish to maintain the efficiency of the table. This means avoiding filling each bucket up too much so that the linear search part takes too much time. If a certain threshold is reached then the number of buckets is increased and the elements redistributed over the hashtable. This is an expensive operation so you try to set up your hashtable with a suitable initial capacity to start with.

Have a look at the code for more details.

Subtract 3 from each element of x which is greater than three

x(x>3)=x(x>3)-3;