{"action":"opened","issue":{"url":"https://api.github.com/repos/RunestoneInteractive/RunestoneServer/issues/693","repository_url":"https://api.github.com/repos/RunestoneInteractive/RunestoneServer","labels_url":"https://api.github.com/repos/RunestoneInteractive/RunestoneServer/issues/693/labels{/name}","comments_url":"https://api.github.com/repos/RunestoneInteractive/RunestoneServer/issues/693/comments","events_url":"https://api.github.com/repos/RunestoneInteractive/RunestoneServer/issues/693/events","html_url":"https://github.com/RunestoneInteractive/RunestoneServer/issues/693","id":141830063,"number":693,"title":"Full HashTable causes infinite loop","user":{"login":"jsonschema","id":1623996,"avatar_url":"https://avatars.githubusercontent.com/u/1623996?v=3","gravatar_id":"","url":"https://api.github.com/users/jsonschema","html_url":"https://github.com/jsonschema","followers_url":"https://api.github.com/users/jsonschema/followers","following_url":"https://api.github.com/users/jsonschema/following{/other_user}","gists_url":"https://api.github.com/users/jsonschema/gists{/gist_id}","starred_url":"https://api.github.com/users/jsonschema/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jsonschema/subscriptions","organizations_url":"https://api.github.com/users/jsonschema/orgs","repos_url":"https://api.github.com/users/jsonschema/repos","events_url":"https://api.github.com/users/jsonschema/events{/privacy}","received_events_url":"https://api.github.com/users/jsonschema/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2016-03-18T10:34:07Z","updated_at":"2016-03-18T10:34:07Z","closed_at":null,"body":"**Active Code 1: Complete Hash Table Example (hashtablecomplete)** in the [chapter on Hashing](http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html) provides the following code for adding a new item to a Hashtable:\r\n\r\n```\r\ndef put(self,key,data):\r\n      hashvalue = self.hashfunction(key,len(self.slots))\r\n      if self.slots[hashvalue] == None:\r\n        self.slots[hashvalue] = key\r\n        self.data[hashvalue] = data\r\n      else:\r\n        if self.slots[hashvalue] == key:\r\n          self.data[hashvalue] = data  #replace\r\n        else:\r\n          nextslot = self.rehash(hashvalue,len(self.slots))\r\n          while self.slots[nextslot] != None and \\\r\n                          self.slots[nextslot] != key:\r\n            nextslot = self.rehash(nextslot,len(self.slots))\r\n          if self.slots[nextslot] == None:\r\n            self.slots[nextslot]=key\r\n            self.data[nextslot]=data\r\n          else:\r\n            self.data[nextslot] = data #replace\r\n```\r\n\r\nThere are two conditions checked, either of which may terminate the while loop:\r\n\r\n```\r\nwhile self.slots[nextslot] != None \r\n   and  self.slots[nextslot] != key\r\n```\r\n\r\n1. Has an empty slot been found?\r\n2. Have we found a slot with a matching key, the value of which should be overwritten?\r\n\r\nHowever, a third must be added to catch the case where the underlying array is full. \r\n\r\n```\r\nwhile self.slots[nextslot] != None \r\n   and  self.slots[nextslot] != key \r\n      and nextslot != hashvalue\r\n```\r\n\r\nAnd the condition should also be handled after the while loop exits:\r\n\r\n```\r\nif self.slots[nextslot] == None:\r\n            self.slots[nextslot]=key\r\n            self.data[nextslot]=data\r\nelif nextslot == hashvalue:\r\n            print 'Hashtable is full!'\r\n            # return something meaningful.\r\nelse:\r\n            self.data[nextslot] = data #replace\r\n```\r\n\r\nFull code:\r\n\r\n```\r\ndef put(self,key,data):\r\n      hashvalue = self.hashfunction(key,len(self.slots))\r\n      if self.slots[hashvalue] == None:\r\n        self.slots[hashvalue] = key\r\n        self.data[hashvalue] = data\r\n      else:\r\n        if self.slots[hashvalue] == key:\r\n          self.data[hashvalue] = data  #replace\r\n        else:\r\n          nextslot = self.rehash(hashvalue,len(self.slots))\r\n          while self.slots[nextslot] != None and \\\r\n                          self.slots[nextslot] != key and nextslot != hashvalue:\r\n            nextslot = self.rehash(nextslot,len(self.slots))\r\n          if self.slots[nextslot] == None:\r\n            self.slots[nextslot]=key\r\n            self.data[nextslot]=data\r\n          elif nextslot == hashvalue:\r\n            print 'Hashtable is full!'\r\n          else:\r\n            self.data[nextslot] = data #replace\r\n```"}}