PREV INDEX NEXT

Author: Stan Eisenstat
Subject: Re: [Cs223] Purpose of Ordering
Date: Thursday, 16 Apr 2020, 20:16:24


    > Message Posted By: Unknown
    >
    > I'm a bit confused as to the purpose of keeping the chaining ordered. I've
    > currently implemented my Hashtable such that if a new entry hashes to the
    > same value, the array corresponding to that hashed-value is given a larger
    > size and the entries are copied over (no strcmp()s are called to order the
    > entries).
    >
    > I don't understand why keeping the array ordered matters because when I
    > perform a search, I am simply performing a linear search on the entries
    > with that particular hash value. It doesn't seem like keeping it ordered
    > would save any time.

As we discussed in class before break, it reduces the
search time for an unsuccessful search.  Moreover, it
allows you to replace linear search with binary search
(which would have made Nine20 too long), which would
make all search faster.

--Stan-
PREV INDEX NEXT