Solution: Hash Tables
Review the solution that implements the addSlow() method in LinearHashTable.
We'll cover the following...
Task
Here is the solution that implements an addSlow() method for adding an element x to a LinearHashTable, which simply stores x in the first null array entry it finds.
Solution
The addSlow() method uses linear probing to handle collisions by sequentially checking the next available slot until an empty slot is found.
Press + to interact
main.py
base.py
utils.py
from utils import new_arrayfrom base import BaseSetimport random# Number of bitsw = 32# Main classclass LinearHashTable(BaseSet):def __init__(self, iterable=[]):self._initialize()self.initialize()self.add_all(iterable)def _initialize(self):self.dl = object()# Initialize functiondef initialize(self):self.d = 1self.t = new_array((1<<self.d))self.q = 0self.n = 0# Function to resize the tabledef _resize(self):self.d = 1while ((1<<self.d) < 3*self.n): self.d += 1told = self.tself.t = new_array((1<<self.d))self.q = self.nfor x in told:if x is not None and x != self.dl:i = self._hash(x)while self.t[i] is not None:i = (i+1) % len(self.t)self.t[i] = x# Helper function for hash codesdef hash_code(self, x):return hash(x)# Function to get hash valuesdef _hash(self, x):h = self.hash_code(x)return (self.tab[0][h&0xff] \^ self.tab[1][(h>>8)&0xff] \^ self.tab[2][(h>>16)&0xff] \^ self.tab[3][(h>>24)&0xff]) >> (w-self.d)# Function to add valuesdef add(self, x):if self.find(x) is not None: return Falseif 2*(self.q+1) > len(self.t): self._resize()i = self._hash(x)while self.t[i] is not None and self.t[i] != self.dl:i = (i + 1) % len(self.t)if self.t[i] is None: self.q += 1self.n += 1self.t[i] = xreturn True# New add methoddef addSlow(self,x):if self.find(x) is not None:return Falseif 2 * (self.q + 1) > len(self.t):self._resize()i = self._hash(x)while self.t[i] is not None:if self.t[i] != self.dl and x == self.t[i]:return Falsei = (i + 1) % len(self.t)if self.t[i] is None:self.q += 1self.n += 1self.t[i] = xreturn True# Function to find valuesdef find(self, x):i = self._hash(x)while self.t[i] is not None:if self.t[i] != self.dl and x == self.t[i]:return self.t[i]i = (i + 1) % len(self.t)# Function to remove valuesdef remove(self, x):i = self._hash(x)while self.t[i] is not None:y = self.t[i]if y != self.dl and x == y:self.t[i] = self.dlself.n -= 1if 8*self.n < len(self.t): self._resize()return yi = (i + 1) % len(self.t)return None# Function to reset the tabledef clear(self):self.initialize()# Iterator functiondef __iter__(self):for x in self.t:if x is not None and x != self.dl:yield x# Hash tabletab = \[[0x0069aeff,0x6ac0719e,0x384cd7ee,0xcba78313,0x133ef89a,0xb37979e6,0xa4c4e09c,0x911c738b,0xc7fe9194,0xba8e5dc7,0xe610718c,0x48460ac5,0x6b4d9d43,0x73afeeab,0x051264cb,0x4b3dba93,0x28837665,0xfb80a52b,0xad1c14af,0xb2baf17f,0x35e311a5,0xf7fa2905,0xa973c315,0x00885f47,0x8842622b,0x0445a92c,0x701ba3a0,0xef608902,0x176099ad,0xd240f938,0xb32d83c6,0xb341afb8,0xc3a978fb,0x55ed1f0c,0xb581286e,0x8ff6938e,0x9f11c1c5,0x4d083bd6,0x1aacc2a4,0xdf13f00a,0x1e282712,0x772d354b,0x21e3a7fd,0x4bc932dc,0xe1deb7ba,0x5e868b8a,0xc9331cc6,0xaa931bbf,0xff92aba6,0xe3efc69f,0xda3b8e2a,0xf9b21ec1,0x2fb89674,0x61c87462,0xa553c2f9,0xca01e279,0x35999337,0xf44c4fd3,0x136a2773,0x812607a8,0xbfcd9bbf,0x0b1d15cd,0xc2a0038b,0x029ab4f7,0xcd7c58f9,0xed3821c4,0x325457c6,0x1dc6b295,0x876dcb83,0x52df45fc,0xa01c9fba,0xc938ff66,0x19e52c87,0x03ae67f9,0x7db39e51,0x74f31686,0x5f10e5a3,0x74108d8a,0x64e63104,0xd86a38d6,0x65be2fbb,0xef06049e,0x9bca1dbd,0x06c63e73,0xe97bd103,0xfed3c22c,0x09d10fc6,0xb92633a3,0x21378ebf,0xe37fa54e,0x893c7910,0xc1c74a5a,0x6c23c029,0x4d4b6187,0xd72bb8fb,0x0dbe1118,0x5e0f4188,0xce0d2dc8,0x8dd83231,0x0466ab90,0x814bc11a,0xef688b9b,0x0a03c851,0xca3c984f,0x6df87ca4,0x6b34d1b2,0x2bad5c75,0xaed1b6d8,0x8c73f8b4,0x4577d798,0x5c953767,0xe7da2d51,0x2b9279a0,0x418d9b51,0x8c47ec3d,0x894e6119,0xa0ca769d,0x1c3b16a4,0xa1621b5b,0xa695da53,0x22462819,0xf4b878cf,0x72b4d648,0x1faf4267,0x4ba16750,0x08a9d645,0x6bfb829c,0xe051295f,0x6dd5cd97,0x2e9d1baf,0x6ed6231d,0x6f84cb25,0x9ae60c95,0xbcee55ca,0x6831cd97,0x2ccdbc99,0x9f8a0a81,0xa0b2c08f,0xe957c36b,0x9cb797b5,0x107c6362,0x48dacf5d,0x6e16f569,0x39be78c3,0x6445637f,0xed445ee5,0x8ec45004,0x9ef8a405,0xb5796a45,0x049d5143,0xb3c1d852,0xc36d9b44,0xab0da981,0xff5226b3,0x19169b4c,0x9a49194d,0xba218b42,0xab98c8ee,0x4db02645,0x6faca3c8,0x12c60d2d,0xaf67b750,0xf0f6a855,0xead566d9,0x42d0cccd,0x76a532bb,0x82a6dc35,0xc1c23d0e,0x83d45bd2,0xd7024912,0x97888901,0x2b7cdd2c,0x523742a5,0xecb96b3b,0xd800d833,0x7b4d0c91,0x95c7dd86,0x88880aad,0xf0ce0990,0x7e292a90,0x79ac4437,0x8a9f59cc,0x818444d1,0xae4e735d,0xa529db95,0x58b35661,0xa909a7de,0x9273beaa,0xfe94332c,0x259b88e4,0xc88f4f6a,0x2a9d33ef,0x4b5d106d,0xdc3a9fca,0xa8061cad,0x7679422c,0xaf72ad02,0xc5799ea5,0x306d694d,0x620aad10,0xd188b9dd,0xeff6ad87,0x6b890354,0xb5907cd3,0x733290fc,0x4b6c0733,0x0bad0ebd,0xa049d3ad,0xc9d0cdae,0x9c144d6f,0x5990b63b,0xfa33d8e2,0x9ebeb5a0,0xbc7c5c92,0xd3edd2e6,0x54ae1af6,0xd6ada4bd,0x14094c5a,0x0e3c5adf,0xf1ab60f1,0x74456a66,0x0f3a675a,0x87445d0d,0xa81adc2e,0x0f47a1a5,0x4eedb844,0x9c9cb0ce,0x8bb3d330,0x02df93e6,0x86e3ad51,0x1c1072b9,0xacf3001b,0xbd08c487,0xc2667a11,0xdd5ef664,0xd47b67fb,0x959cca45,0xa7da8e68,0xb75b1e18,0x75201924,0xe689ab8b,0x0f5e6b0a,0x75205923,0xbba35593,0xd24dab24,0x0288caeb,0xcbf022a9,0x392d7ee5,0x16fe493a,0xb6bcadfd,0x9813ec72,0x9aa3d37c,0xee88a59e,0x6cdbad4e,0x6b96aabf,0xcb54d5e5],[0x116fc403,0x260d7e7b,0xdef689e7,0xa5b3d49a,0x921f3594,0xb24c8cba,0x1bdefb3f,0x6519e846,0x24b37253,0x1cc6b12b,0x6f48f06e,0xca90b0db,0x8e20570b,0xda75ed0f,0x1b515143,0x0990a659,0xdcedb6b3,0xec22de79,0xdd56f7a9,0x901194a6,0x4bf3db02,0x5d31787d,0xd24da2ca,0x9fc9bc14,0x9aa38ac9,0xe95972ba,0x8233a732,0xb9d4317e,0x51f9b329,0x94f12c56,0x1ace26e4,0xecda5183,0x1353e547,0x39b99ab3,0x6413ac97,0xeb6b5334,0xdd94ed2b,0x298e9d2c,0xd38abc91,0x3f17ee4e,0x99f8931d,0x88bae7da,0xb5506a36,0x2d7baf6d,0x42a98d2b,0xbb9b94b9,0x58820083,0x521bba4c,0x76699597,0x137b86be,0x8533888e,0xb37316dd,0x284c3de4,0xfe60e3e6,0x94edaa40,0x919c85cd,0x24cb6f23,0x6b446fbd,0xbe933c15,0x2a43951a,0x791a9f90,0x47977c04,0xa6350eec,0x95e817a5,0xffc82e8c,0xad379229,0x6ec9531a,0x8cab29f9,0xb2f18402,0xd0ebdac1,0xd7b559b4,0x7ad30e7c,0xe1d1adb7,0x58a66f9c,0x7a26636a,0x8c865f92,0x65363517,0x732b87db,0x64a1ad52,0x72e87c39,0x0b943e4d,0x532d3593,0xedcf9975,0x44b5bec1,0x13ac91f8,0x6e6f3a76,0x36ac3c6d,0x528a3ecf,0xf3d8cd75,0x8facd64c,0xdb4d13d5,0x80d49a67,0xaa7061d3,0x9486ba8d,0x7454a65b,0x18e7b707,0xd9cc05b9,0x44eb014d,0x28ba26d8,0xa8852791,0xf8dc3053,0xabe46b52,0x9e261d1f,0x768f83dd,0x1c888838,0x6d9b9ce6,0x69e82575,0x2959538f,0xd0ff9685,0x92b4540c,0x7c93035b,0x7cad90ad,0x49aaa908,0x3981f4b8,0x191f4339,0xd0971bfc,0xa7209692,0x0e253cad,0x40e2ee61,0xc5c63486,0xdf4f238b,0x2d3cb89a,0x3b5704b2,0xcc14c2cb,0xb1698d38,0x079c3b9b,0xbb3867e4,0x9f01e223,0x35e69012,0x5c87d888,0x2cea4193,0xee088da5,0x0ea4d5ab,0x8a4906e8,0xf6e5e283,0xee87fa18,0x9f96c751,0x947252c0,0x9b50b97e,0x05952521,0x9440f5ae,0xa0642786,0xebcc62be,0xadccf011,0x00b863e6,0x1c3ab5b3,0x7c701e4b,0xa9565792,0xb1ad459c,0x833ba164,0x89544ae3,0x35540c75,0x198d0fec,0xbe93bf33,0xc28444b3,0xbc3add48,0xb4300c14,0xee0ed408,0xca08ada3,0x0be06480,0xc4dd8ce2,0x61195564,0x5b10a111,0x65cd2b3b,0xcbeb06ae,0xfce70080,0xef40b102,0xfc0bfe6f,0x8111bf20,0xfb166db1,0x3598b2ef,0x1e0e04de,0x1bf7cf2d,0x0de7eaf1,0x829457e0,0xe8865341,0x826272ad,0xb57db2a4,0x7413e6e7,0x416323ff,0x8e08d503,0x1da4dfac,0x983b9a78,0x0fab5fe0,0x585e7a90,0x038cf73c,0xecf90d31,0x046055c8,0x59926d71,0x06959f1f,0x3b8290b7,0x0bb834d9,0xa0dc5bec,0xec9ae604,0x6ebfd59d,0xfeccbab5,0x240bd4ba,0x2df2b232,0xe14e0383,0xd86526ec,0xe3d974fc,0x940662b5,0x81abf5d4,0x8010e6eb,0x700d9849,0x040d0c42,0xc980417b,0x95fa374a,0x724b1448,0x217205ec,0x0153b4bb,0xea55ea92,0x2049d5a1,0x82576f06,0x586fcfeb,0xa975e489,0x14c862e9,0xacb8b52c,0x2f3fb91e,0xce273650,0x66608f4a,0x24f81bb7,0x0382dc34,0x07bdc163,0xc42ad034,0xe63cf998,0x1a61f233,0xd5754ebe,0x37275214,0x2322de2a,0x3a53b9b4,0xab9c6963,0x2f3a51be,0x5066e7c7,0x941bda97,0x75fadceb,0xd05ad081,0xf77d5daf,0xd9879250,0xebf8bf97,0x65be4a70,0x388eda48,0x728173fb,0x05975bfa,0x314dad8a,0x2cb4909f,0xc736b716,0x9007296d,0x4fd61551,0xd4378ccf,0x649aac3e,0xd9ca1a9d,0x16ff16ae,0x8090f1c5,0xfe0c4703,0xc4152307],[0xf07e5e34,0x62114ba6,0xf45ffe22,0xbaa48702,0xe27e48a4,0xc43b4779,0x549a4566,0x93bc4836,0x3b2e8d46,0x3f8a77ae,0x71e2d944,0xc09c5dce,0xebfbfd4f,0x7f8e1c40,0x3c310a69,0x52f62f09,0xb7fd11bb,0xa9d055a7,0xe3bd4654,0x9696ae10,0xdf953225,0x42fd2380,0x69756e5c,0x9d950bc4,0xe2beea59,0xd33daa07,0xe97d31ce,0xd9fb0a49,0x553a27f2,0x7166586f,0xeb04d48c,0x72adb63a,0x340ab99e,0x459b4609,0x481421b7,0x7db83c71,0x192f6c22,0x711852a8,0xc6bd6562,0xb91be2c8,0xefe89dbf,0xc404eb9b,0x9ebc1bc7,0x8dc7eed2,0x4d84efd7,0x0783d7e5,0x3b5ca2f2,0x9997e51c,0x89b432c9,0x72ae9672,0x61d522d9,0xa639fd45,0xa7da3b46,0x696e73ec,0x89581a95,0x4aa25f94,0xd0eb2a48,0x04865f68,0x1cbd651a,0xd6b2afd9,0xd401b965,0xd20aa5a7,0xc0aa1b15,0xfb4ce7af,0x159974c5,0x15d0841d,0x6b2836b4,0xef3b3edf,0xaf2db0b3,0x13106fb6,0xff41d7f9,0xab2a698d,0x68e04dc9,0xe5ee0099,0xe50d4017,0x5ea78d6d,0x2e18fb07,0xfe22b9ff,0x544c05f1,0xc2e10853,0x8d151bd6,0x17ee763a,0xa663ce31,0x4a4b5e33,0x298b13c1,0xd3b40c89,0x121b6b4e,0x59cf0429,0x3d0bab9d,0xd24c5dfe,0x5bb7349f,0xac5dbfe9,0x7eca5ebb,0xadb8b3e3,0x71ab540b,0xc8e3dc0d,0x12e6cd3f,0x8197f22c,0x5ff77265,0xe5641dbc,0x818ab24c,0x627b98f7,0xdd84e1d6,0x531c2346,0xec2f4e3c,0x4a3cb318,0x70cb24fe,0x35c17bfe,0xec91fd18,0x6efb3c18,0x16908369,0x41732188,0x449e658b,0x2e9931cb,0x67cd066e,0x883ca306,0xf66aecac,0x979bf015,0x8e85e27d,0x0560372b,0x987995d6,0xaff98ed7,0x552ee87b,0x21a53787,0x3d3cfd45,0xa084dae0,0x8c91be2f,0xac4c3550,0xa7db63ff,0x124b2f23,0x95d05d4e,0xb983db13,0xa929a3c1,0x111cd0a0,0xf59ded9a,0xce677ae3,0xfa949e59,0xd673e658,0xf8c8e27b,0x3c60fc3d,0x59a4f230,0xf54a5e87,0x08cff440,0xd4bbb1ee,0x6a0c7db0,0xecbaa99d,0xec61dcaf,0xf1056e2b,0x54236899,0xadad347c,0xc9885bc9,0x2fe2a4ec,0x01ba2b86,0x6b23f604,0xb354ef08,0x6a3dc5e2,0xab61da36,0x7543925a,0x0a558940,0x48d4d8f3,0xd84f2f6f,0x6ac5311c,0xcd1b660e,0x51293d3d,0xa0f15790,0xd629cd78,0x89201fa5,0x46005119,0x9617fa14,0xc375a68b,0x7ccb519b,0x6420a714,0xb736d2ce,0x154fcf4a,0x71cad2f5,0xacb150d7,0x97bc8e36,0xc5506d0a,0xa9facc35,0x1a9630db,0xbd3d72ee,0x58cdf27c,0x17f3e1f9,0x41598836,0xd6adac30,0x309a5b3f,0x3bd3aa32,0x40f08f50,0xf37cbd6c,0xcbdb8aef,0xe0819189,0x5a9b663b,0x6932a448,0xb1b3e866,0xc50ee24d,0xad999126,0xafb04056,0xc95974e5,0x636a64fa,0x0bb12dd9,0x78caa164,0xd26a7ec8,0x451a0b53,0x6d00aac6,0x484d1d9d,0x39728dd4,0xfbfec2ea,0xa6d5aaf9,0x91c4f6ea,0x31cab009,0x9b6ba4e8,0xe271ed67,0x4c87a84d,0x8a1a4567,0x93749497,0xc566edcc,0xc8229554,0x927925fd,0xad1caced,0xdc24f7ed,0xc92b9220,0x936cd037,0xbd2d0256,0x5c92409b,0xa3aa2682,0x4da97646,0xbcfdec81,0x25d5b61d,0x20e1660d,0x4b5214ed,0x91aa596a,0xb241415c,0x88ec91a1,0x2375e939,0x981ad627,0x4a54ee18,0x13d98660,0x9375c64d,0x538d3b28,0x4bf37ca7,0x192b351e,0x3cacf215,0x3ecf3565,0x50f5c0fc,0xaafe3d4e,0x6351b4f5,0x1b800d4f,0xfad73cdf,0xe300e1d8,0xb2cb5b04,0xfb019702,0xfb647f85,0x375a7b74,0xed6a6760,0x45c54e76,0x06524d79],[0x48722ec4,0x8a2694db,0x3cf80478,0xf9bc47ba,0x76b258fb,0xf71a1ec6,0x841189df,0x1a866461,0x72b5488c,0x71663983,0xbda59407,0xa2b68f85,0x62dbd0aa,0xe4966aa3,0x32e0efaa,0x71bb3699,0x2eda14a6,0x53f8917c,0x874974ce,0xe680bcca,0x96a9c462,0x399ca451,0xc46616f5,0xeee71114,0x5878e472,0x3a83c559,0x54862a18,0x82aea480,0x492d0019,0xd62a7027,0x36655f50,0xce412fdf,0xc8136871,0xd6cfe1d8,0x121c9c91,0x13abbf51,0x3aaa7037,0x9f6e7cb6,0xae82c4c4,0x55fdce32,0xd8dd6bda,0xd6ec4938,0x6a5aee52,0x52c8a764,0xa6a85297,0x5131de9e,0x396a6599,0xe27b1100,0xe68588d3,0x7b89a612,0xad48a7a4,0xfd205673,0x81807089,0x239d2d38,0x39518df3,0x256f3f14,0x5c65e7b8,0x64caebdc,0xd8d694b6,0xb4a87da3,0xa651881e,0xca1d252d,0x993a3ddc,0x14f9a54d,0x6b14d2ff,0xbbed03bb,0x8d12bc03,0x6cce455d,0x613d6487,0x6d04ce6a,0xc2f4c84c,0x306d8ff2,0x584a9847,0x68902fc5,0x70af1a4f,0x3ab4cb98,0xe8be4453,0x7e95d355,0x84b0f371,0x4c5ccb52,0xdd6d029c,0xafa47124,0x71aabf91,0xd3407f95,0xe7fa3a9c,0x4f634405,0x0cbf2cb7,0x0192ff17,0x296959dd,0x9e4d34d5,0xfd9a4286,0xac7b6933,0x4650f585,0x168af40d,0x73816119,0x5542d96d,0x99047276,0x1b5bbe67,0x01a8209e,0x6f9db32e,0xd762bbd1,0x299a3804,0x87abe66d,0xd479eeaa,0x79928f4e,0x3937ffbc,0x3c8e83ca,0x2a8f9347,0x4d2324d3,0xf0183dda,0x9fbedb15,0xac365889,0xf1be552c,0xa4b32d5a,0xdc77fff3,0x9d516da8,0x7f3c347c,0x39e8479f,0x9e869687,0x6a160347,0x49ab7403,0x830d31c7,0x11311354,0x79e6cc69,0x35b25caa,0x398af9aa,0x02ef4356,0xb5ecba53,0x666d6c8b,0x8836b3ae,0x23b9fc98,0x0cc8e3d0,0x3ad594e1,0xb124529d,0xe059c1de,0xfa88e0d9,0xba117846,0x1782a65a,0xee9f80f9,0xbc9aec55,0x88aec1d4,0x9c3907fa,0x92b7b5bf,0x464acbf4,0xbbbd04a8,0xf0e966bf,0x14c5f971,0x83018d49,0xfaf4fc0a,0x3b4639b2,0x6b7e297d,0xc0e9a807,0x418713d3,0x1a2b2361,0x80850d90,0xd515816e,0x3deb48ea,0x6bfe6aa1,0x3680036c,0x228e76ae,0x78f16c87,0xff4d85ea,0x7d831974,0xba962d6b,0x4bae0b1d,0xc0db431a,0x04b46400,0xcf427175,0x244e321d,0x1c8b1fc9,0x63a2b794,0x1939d9c6,0xc92a530e,0x21a8e5ad,0x28050194,0x3b106223,0xb21e2ce1,0x7ae71fe4,0x7f7759f0,0x0329c8f4,0xd09f6b37,0x897e12a5,0x4103c4b1,0x56520dae,0x5d7391aa,0x7ac9f12d,0xeac6b834,0x99f8f6a8,0x2867867a,0xff6f3343,0x3167097a,0x38432d1d,0x108377f8,0xfd8e0d5f,0x25e15692,0xf00d40f9,0x1f1276f3,0xb748c8cd,0x6dbb9d9c,0x99ab7ceb,0xa4a9784f,0xcb4b2535,0xb3eb5ca7,0xd3a09e75,0x90f3ee7e,0x28ef2a57,0xbdb643a2,0x1112ab10,0x546b1af2,0x8c41e90d,0x0f5fcd88,0x6f259f40,0x34b33966,0x5f3558d7,0xfff36f0b,0xa3459449,0xdcecbce1,0x69ff2bf7,0x7525e1da,0x24c9de72,0xea9626b1,0x87c7385d,0x15e4211e,0x9f7ef269,0xfed018d1,0x7632076c,0x8d4f0157,0x10c1205a,0x65db0e00,0x813f0e8b,0xbafea255,0xb47e6663,0x2a0eba78,0xf66b3783,0xfff1db48,0x47997f03,0x3a49e877,0x4536a0b5,0x89b0738f,0xf5758b5e,0x1d277388,0xf5db28e8,0xb4ef0add,0x776fed12,0x045b614a,0xc95f47ae,0x13a1d602,0x217d6338,0xc509d080,0x006789de,0xd891cccc,0xb02f9980,0x67f00301,0xafc87999,0x043d8fbd,0xb32d6061]]if __name__ == "__main__":# Random number generatorrand = random.Random()# Creating objectlht = LinearHashTable()n = 100# Adding valuesprint("Adding")for i in range(n):x = rand.randint(0, n)rlht = lht.addSlow(x)# Searching different valuesprint("Searching")for i in range(10):x = rand.randint(0, n)rlht = lht.find(x) is not Noneif rlht:print("The value", x, "is found")else:print("The value", x, "is not found")lht.clear()
Explanation
This code snippet defines a method addSlow within a class. Here’s an explanation of each part: