Hello.
This is something I came up with in order to assign a number to names, like an index if you like for lookup purposes, so I can get back the name, by the index number I retrieved when I stored the name into the table. -I also needed the id number to be static, and independent of any deleted/inserted items, which is whay I use a table by design, and not a regular AppleScript list, where the item numbers will vary with insertions and deletions.
It is a replacement for a hash-table, and is is calibrated to hold less than 100 items, although it will search for a free spot (deleted item), should it be full, before it errors. It has a much better performance than a hash table of that size, the downside is that the keys aren’t encrypted in anyway, but that is outside of my requirements.
I use this for translating names into indicies, since some algorithms are better at working with indicies than names, (like matrices of various kinds, adjacency matrices in my case).
Why not use a hash table?
Because, I calculated the probabilities for a collision on such a small table, and I found the probability for a collison to be almost 100%, with a filling of 50 elements, for a table size of 100.
The formulae for the probability of a hash collision is 1 - e^(-k(k-1)/2N) where k is the number of elements, and N is the size of the hash key. For 15 elements, this yields a probability of a hash collison of 0.56 ~ 56%, for 50 elements, the probability is almost 100%.
The hash key I used was really much larger than 7bits, but if you are setting 100 elements as the max number of elements, then 100 is the 7 bit number we have to relate to, since we have to use the hash key modulus 101, to get elements between 1 and 100, which is what the hash keys will be “concentrated” down to (a span of values over 7 bits, since we need 7-bits to represent the decimal number 100 as a binary number).
Reference:
Hash Collision Probabilities
on makeidTable()
script idTable
-- 100 empty strings
property table : {"", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""}
property elmPtr : 1
on assignID(aName)
if elmPtr < (length of my table) then
set item elmPtr of my table to aName
set assignedId to elmPtr
set elmPtr to elmPtr + 1
return assignedId
else
set emptyItem to false
repeat with i from 1 to (length of my table)
if item i of my table is "" then
set emptyItem to i
exit repeat
end if
end repeat
if emptyItem is not false then
set item emptyItem of my table to aName
return emptyItem
else
error "assignID: the table was full, holding " & my elmCount & " elements."
end if
end if
end assignID
on remvName for anId
set item anId of my table to ""
end remvName
on aName for anId
return item anId of my table
end aName
end script
end makeidTable
set ids to makeidTable()
set idlist to {}
set end of idlist to ids's assignID("London")
set end of idlist to ids's assignID("Oslo")
set end of idlist to ids's assignID("Sidney")
set end of idlist to ids's assignID("Zurich")
set end of idlist to ids's assignID("Geneva")
set end of idlist to ids's assignID("Paris")
set end of idlist to ids's assignID("Rome")
set end of idlist to ids's assignID("Torino")
set end of idlist to ids's assignID("Vienna")
set aCity to aName of ids for 4
--> "Zurich"
Edit
2015-04-25 22:45 CET: I have edited the documentation so that it should be a bit clearer, what it is, the purpose, and why the design.
