I wanted to know how your program worked and so I removed all the module level checking code and used the following:
table = []
def check(key, value):
global table
table = insert(key, value, table)
print table
print get(key, table)
check(5, 'value')
check('key', 'value2')
check('key', 'value3')
check('key2', 'value4')
This gave me a somewhat strange output.
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [5, ['value']], [], [], [], [], []]
['value']
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [[], [], [], [], [], [], ['key', ['value2']], [], [], [], [], [], [], [], [], [], [], [], [], [5, ['value']], [], [], []], [], [], [], [], []]
['value2']
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [[], [], [], [], [], [], ['key', ['value2', 'value3']], [], [], [], [], [], [], [], [], [], [], [], [], [5, ['value']], [], [], []], [], [], [], [], []]
['value2', 'value3']
[[], [], [], [], [], [], [], [], ['key2', ['value4']], [], [], [], [], [], [], [], [], [[], [], [], [], [], [], ['key', ['value2', 'value3']], [], [], [], [], [], [], [], [], [], [], [], [], [5, ['value']], [], [], []], [], [], [], [], []]
['value4']
The keys `5` and `key` collide and so the results should be a list of two items, but you spam it with lots of items.
This can be due to two things:
- A bad algorithm that spams `list.append`
- Your algorithm being a 'hash-tree' not hash-table.
From the looks of your algorithm it's probably the latter.
This is as you do:
entry = table
for i, char in enumerate(key_hash):
ordinal = ord(char) - 48
entry = entry[ordinal]
This is fine and all, but then it's not a hash-table.
A hash-table should be a 2D-table of items. Where items here is just a `[key, value]` pair.
If you change your code to a hash-table then it'd be so much more simpler.
The algorithm is hash key, modulo it, append to table:
def add(key, value, table):
hashed_key = hash(key) % len(table)
table[hased_key].append([key, value])
This should bring up some concerns:
1. What if the size of the table changes?
2. What if the key is already in the table?
3. What if the key is already in the table and the size of the table changes?
These can be resolved, (1) by using a class, (2) by checking the list.
class Dict(object):
def __init__(self, size=8192):
self._table = [[] for _ in xrange(size)]
self._mod = size
def _get_item_index(self, key):
hashed_key = hash(key) % self._mod
list_ = self._table[hashed_key]
return list_, next((i for i in xrange(len(list_)) if list_[i][0] == key), None)
This then makes `insert` and `get` easy to make.
def insert(self, key, value):
list_, index = self._get_item_index(key)
if index is None:
list_.append([key, [value]])
else:
list_[index][1].append(value)
def get(self, key):
list_, index = self._get_item_index(key)
if index is None:
raise KeyError(key)
return list_[index][1]
Your method seems alright, it's hard to read, and is way more complex then it needs to be, so I'd recommend at least making a `_get_item_index` if you do carry on with your hash tree.
But it seems faster than my one.
---
For in-depth review of the code:
If I were to make `_get_item` then I'd look at the `get` function first.
I don't think that you should have `pop` in that function, and so I'll remove it.
This leaves you with:
def get(key, table):
key_hash = hashlib.sha1(str(key)).hexdigest().upper()
entry = table
for i, char in enumerate(key_hash):
ordinal = ord(char) - 48
entry = entry[ordinal]
entry_len = len(entry)
if entry_len is 0:
raise KeyError(key)
elif entry_len is 2:
return entry[1]
raise KeyError(key)
From this we can see the basic looping structure. I'd first merge ordinal with entry, to get `entry = entry[ord(char) - 48]`.
You shouldn't use `1 is 1` instead use `1 == 1`, it makes more sense as `1 == 1.0` is true where `1 is 1.0` is not.
As we need to get the item, `entry`, even if it's not there (we'll be using this for `update` too), we should change the `if`s to just return the entry.
Finally you should notice that `entry_len == 0` is the same as `not entry`.
Merging these all together gets us:
def _get_item(key, table):
key_hash = hashlib.sha1(str(key)).hexdigest().upper()
entry = table
for i, char in enumerate(key_hash):
entry = entry[ord(char) - 48]
if not entry:
return entry
elif len(entry) == 2:
return entry
else:
raise KeyError(key)
To use it is simple:
def get(key, table):
item = _get_item(key)
if item and item[0] == key:
return item[1]
raise KeyError(key)
We still need to get `_get_item` working for `update` however.
You should be able to see that the code is _roughly_ the same for all except `elif entry_len is 2:`.
To help with this we should break out of the loop so that we're in a 'separate environment'.
To make things simpler I'd also return if `key == entry[0]`.
And so:
elif len(entry) == 2:
if key == entry[0]:
return entry
break
You should notice that we don't want the new code to run if we are using the other version of this function.
To do this we can pass a flag that returns the entry after exiting the for.
if extend:
return entry
Finally we're left with:
extant_key, extant_values = entry[0], entry[1]
del entry[:]
#entry = []
extant_hash = get_hash(extant_key)
for i in xrange(i + 1, len(key_hash)):
char, extant_char = key_hash[i], extant_hash[i]
if char == extant_char:
entry.extend(alphabet())
ordinal = ord(char) - 48
entry = entry[ordinal]
#entry = []
else: break
if char != extant_char:
entry.extend(alphabet())
char_ord = ord(char) - 48
entry[char_ord].extend((key, [value]))
extant_ord = ord(extant_char) - 48
entry[extant_ord].extend((extant_key, extant_values))
#entry has empty lists except 2
break
else: pass
#hash collision, to be continued
This leads to the following changes:
- Using both `extant_key` and `extant_value` is more verbose than I like, and would just use `extant` with the slice `item[0:2]`.
- Use `izip` rather than `xrange(i + 1, len(key_hash))`.
This is quite simple add `from itertools import izip` at the top, and then use:
for char, extant_char in izip(key_hash[i + 1:], extant_hash[i + 1:]):
- Use `item[ord(...) - 48]` rather than setting intermarry variables.
- Raise an error if you don't break out the for loop.
- Change the if to `char != extant_char` and then break.
This adds a little bit of readability, and prevents large amounts of indents.
- Finally `return entry[ord(char) - 48]`.
This should lead to something like:
extant = entry[0:2]
del entry[:]
extant_hash = get_hash(extant[0])
for char, extant_char in izip(key_hash[i + 1:], extant_hash[i + 1:]):
if char != extant_char:
break
entry.extend(alphabet())
entry = entry[ord(char) - 48]
else:
raise KeyError(key)
entry.extend(alphabet())
entry[ord(extant_char) - 48].extend(extant)
return entry[ord(char) - 48]
Finally I should note that the two `KeyError`s raised in this function, aren't really errors with the key, it's actually that there is actually a sha1 collision.
And so I'd change the errors to custom errors.
What is the likelihood of these? [Not very likely][0] but [my favorite programmers.SE answer][1] makes me think that ruling this out is not a good idea.
[0]: http://crypto.stackexchange.com/a/2584/13004
[1]: https://softwareengineering.stackexchange.com/a/145633/142543