A toy example of implementig a hash table in matlab

hashTableDemo.m

function demo
% This is a toy example of implementig a hash table in matlab
    hashBits = 20;
    
    function h = hash(s)
        % A toy hash function for vectors/strings
        % Note this function accepts a matrix as input thus is fast in matlab
        h = mod(sum(s, 2), 2^hashBits) + 1; % Note this produces a 16-bit hash code. 
        % Plus one to prevent outputting 0 as hash code, which will cause 
        % problems in the following code.
    end

    function indices = generateIndices(hammingDist, hashCode)
        % Generate indices of hash table with hamming distance <= hammingDist
        % from the hashCode.
        deltaIndices = [0];
        for dist = 1: hammingDist
            delta = nchoosek(1: hashBits, dist);
            deltaIndices = [deltaIndices; sum(repmat(2, size(delta, 1), dist) .^ delta, 2)];
        end
        
        indices = bitxor(repmat(hashCode, size(deltaIndices, 1), 1), deltaIndices);
        indices = indices(indices <= 2^hashBits - 1);
    end

data = randi(100, [1000, 20]); % First we get some input vectors
hashes = hash(data); % Hash them.
% And then create a hash table
hashTable = cell(2^hashBits, 1);
for i = 1: length(hashes)
    % This generates an invert index. So that with a given hash value, we
    % can retrive all the elements with the same value in O(1) time.
    hashTable{hashes(i)} = [hashTable{hashes(i)}; i];
end
% Now given a new element, we can get its neighbor (in terms of one
% single hash function) rapidly.
query = randi(100, [1, 20])
fprintf('Neighbors:\n');
indices = generateIndices(2, 1);
for i = 1: length(indices)
    if (length(hashTable{indices(i)}) ~= 0)
        hashTable{indices(i)}
    end
end

end