it should take no longer to search a 4000 slot table with 40,000 items than it would to to search a 40 slot table with 400 items?
Kelder explanation of a hashtable was/is the same as my understanding of them also.
However It IS going to take longer to search a 40,000 item table at 4000 slots than a 400 item table at 40 slots, since theres 100 times the data
if u ment "is it going to take the same time to search a 40,000 item table at 4000 slots as to 40 slots" I would guess its likely the same, it well be a seqental search down the array.
On note to add, to my understanding and this is really not an issue with kelders explanation which i found very good. if two items both have the same hashed index value, rather than a mini list being created, there is a linking value in the already used item which links to the next item held later in the array. Even this is a bit hard to explain (for me)
say you said
/hmake BLAH 10, you get
/hadd blah fred alpha lets assume this hashs to 4
/hadd blah bill beta lets assume this hashs to 7
/hadd blah dave charlie lets assume this hashs to 4
/hadd blah pete delta lets assume this hashs to 4
/hadd blah mike echo lets assume this hashs to 9
slot ref# link# itemname itemvalue
0 4 - - -
1 - - - -
2 - - - -
3 - - - -
4 7 11 fred alpha
5 - - - -
6 - - - -
7 9 - bill beta
8 - - - -
9 11 - mike echo
10 - - - -
11 12 12 dave charlie
12 - - pete delta
13 - - - -
14 - - - -
15 - - - -
The ref# may or maynot exist, its just a pointer to the next next item in array order sometimes it has a backward pointer to the previous one as well, this waas done in FILE stored hashtables more than memory ones, and was designed to reduce disk reads, if you were moving through sequetially, since you wouldnt have to read all the blanks to find the next item.
Whats more the point i was trying to get to, is in this example 3 items (fred,dave,pete) hashed to slot 4, so when fred filled slot 4, and then dave was added, it added a link# to a free slot (beyond the table size of 10) at which dave and its data was stored, when pete was added at 4, first fred was there at 4 that linked to dave at 11 and then another link was added to 12 at which pete was added.
* a note here im not saying this is how mirc actually stores them, however it is my understanding of how a hash table works, in its simplest form, i beleive there is some more advanced calculation on how it actually gets the free slot positions (ie 11 & 12) than just assigning the next free, but for here i just used the next avalaible.
I beleive this is the reason for the aparent randomness of order of entries in a hashtable if you try and seqentially few them.
Just to add to the confusion I have seen a hashtable system where it uses a disecting tree system to store items
* i might have got some of that table wrong there and i wouldnt even like to go into how its worked out, as it gave me a sore head years ago when i had to code one.