[H,ID,NEXT] = VL_IHASHSUM(H,ID,NEXT,K,X) counts the number of occurences of the columns of X, accumulating these to the hash table represented by the tripled H,ID,NEXT.
X is a D x N array of class UINT8 each row of which defines an D dimensional label. Labels cannot be all zeros.
H and NEXT are 1 x C arrays of class UINT32 and ID is a D x C array of class UINT8. H is a vector of counts, ID stores, for each element of H, the corresponding label, and NEXT is a vector of indexes.
Once constructed, the hash table can be searched by means of the VL_IHASHFIND() function.
The hash table uses double hashing [1] with an initial size equal to K (so that C >= K). Given a label X, this is first hashed by using the FNV algorithm [2] to one of K bucket. If this bucket is free, it is assigned to label X and the count is incremented. If the bucket is already assigned to the same label X, the count is incremented. If the bucket is already assigned to a different label, a second hash is used to scan (probe) the table for a free bucket.
If no free/matching bucket is found (because the hash table is full) an overflow area containing extra buckets is used. This is visited by reading off indexe from the NEXT vector, until a matching bucket is found or the overflow area is enlarged.
- Example
The following example counts integer bi-dimensional label occurences:
K = 5 ; h = zeros(1,K,'uint32') ; id = zeros(2,K,'uint8'); next = zeros(1,K,'uint32') ; X = uint8([1 1 ; 1 2 ; 2 1 ; 1 1]') ; [h,id,next] = vl_ihashsum(h,id,next,K,X) ;
resulting in
h = [1 0 1 2 0] id = [1 0 2 1 0 2 0 1 1 0] next = [0 0 0 0 0]For example, [1;2] has a count of 1 and [1;1] has a count of 2. NEXT is zero because there have been no collisions.
- REFERENCES
[1] http://en.wikipedia.org/wiki/Double_hashing [2] http://www.isthe.com/chongo/tech/comp/fnv
See also: VL_IHASHFIND().