Skip to content

Instantly share code, notes, and snippets.

@kom-bu

kom-bu/ChainedHashSet.ipynb

Created June 12, 2020 01:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kom-bu/a9813d85b34009bc4d8f7f70fcce194e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kom-bu/a9813d85b34009bc4d8f7f70fcce194e to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
ChainedHashSet.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from random import randrange\n",
"class CHashSet:\n",
" def __init__(self):\n",
" self.array = []\n",
" self.length = 0\n",
" self.loglenarr = -1\n",
" self.seed = 2 * randrange(2**31) + 1\n",
" def __len__(self):\n",
" return self.length;\n",
" def hash(self, x):\n",
" res = (self.seed * x) % 2**32 >> (32 - self.loglenarr)\n",
" #print('#'+str(x)+'='+str(res))\n",
" return res\n",
" def add(self, x):\n",
" if type(x) is not int or not (0 <= x < 2 ** 32):\n",
" raise ValueError('only int32 allowed')\n",
" if self.find(x) is not None:\n",
" raise ValueError('value already exists')\n",
" if len(self) >= len(self.array):\n",
" self.resize()\n",
" self.array[self.hash(x)].append(x)\n",
" self.length += 1\n",
" def remove(self, x):\n",
" if self.find(x) is None:\n",
" raise ValueError(\"value doesn't exist\")\n",
" self.array[self.hash(x)].remove(x)\n",
" self.length -= 1\n",
" def find(self, x):\n",
" if self.length == 0:\n",
" return None\n",
" for item in self.array[self.hash(x)]:\n",
" if x == item:\n",
" return x\n",
" return None\n",
" def resize(self): # twice except 0\n",
" oldarray = self.array\n",
" self.loglenarr += 1\n",
" self.array = [[] for _ in range(2 ** self.loglenarr)]\n",
" self.length = 0\n",
" for l in oldarray:\n",
" for item in l:\n",
" self.add(item)\n",
" def debug(self):\n",
" for l in self.array:\n",
" print(l)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"hs = CHashSet()"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"hs.add(100)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"hs.add(123)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[100]\n",
"[123]\n"
]
}
],
"source": [
"hs.debug()"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"hs.add(9)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[]\n",
"[100]\n",
"[123, 9]\n",
"[]\n"
]
}
],
"source": [
"hs.debug()"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"123"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hs.find(123)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"hs.remove(9)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[]\n",
"[100]\n",
"[123]\n",
"[]\n"
]
}
],
"source": [
"hs.debug()"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"hs.find(9)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"hs.add(8)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[]\n",
"[100]\n",
"[123]\n",
"[8]\n"
]
}
],
"source": [
"hs.debug()"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"hs = CHashSet()"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"for i in range(100):\n",
" hs.add(i)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0]\n",
"[35]\n",
"[70]\n",
"[]\n",
"[27]\n",
"[62]\n",
"[]\n",
"[19, 97]\n",
"[]\n",
"[54]\n",
"[89]\n",
"[11]\n",
"[46]\n",
"[81]\n",
"[3]\n",
"[38]\n",
"[]\n",
"[73]\n",
"[]\n",
"[30]\n",
"[65]\n",
"[]\n",
"[22]\n",
"[57]\n",
"[]\n",
"[92]\n",
"[14]\n",
"[49]\n",
"[84]\n",
"[6]\n",
"[41]\n",
"[76]\n",
"[]\n",
"[]\n",
"[33]\n",
"[68]\n",
"[]\n",
"[25]\n",
"[60]\n",
"[95]\n",
"[17]\n",
"[]\n",
"[52]\n",
"[87]\n",
"[9]\n",
"[44]\n",
"[79]\n",
"[1]\n",
"[36]\n",
"[]\n",
"[71]\n",
"[]\n",
"[28]\n",
"[63]\n",
"[98]\n",
"[20]\n",
"[55]\n",
"[90]\n",
"[12]\n",
"[]\n",
"[47]\n",
"[82]\n",
"[4]\n",
"[39]\n",
"[74]\n",
"[]\n",
"[31]\n",
"[]\n",
"[66]\n",
"[]\n",
"[23]\n",
"[58]\n",
"[93]\n",
"[15]\n",
"[50]\n",
"[]\n",
"[85]\n",
"[7]\n",
"[42]\n",
"[77]\n",
"[]\n",
"[34]\n",
"[69]\n",
"[]\n",
"[]\n",
"[26]\n",
"[61]\n",
"[96]\n",
"[18]\n",
"[53]\n",
"[88]\n",
"[10]\n",
"[45]\n",
"[]\n",
"[80]\n",
"[2]\n",
"[37]\n",
"[72]\n",
"[]\n",
"[29]\n",
"[64]\n",
"[]\n",
"[99]\n",
"[21]\n",
"[56]\n",
"[91]\n",
"[13]\n",
"[48]\n",
"[83]\n",
"[5]\n",
"[]\n",
"[40]\n",
"[75]\n",
"[]\n",
"[32]\n",
"[67]\n",
"[]\n",
"[24]\n",
"[]\n",
"[59]\n",
"[94]\n",
"[16]\n",
"[51]\n",
"[86]\n",
"[8]\n",
"[43]\n",
"[]\n",
"[78]\n"
]
}
],
"source": [
"hs.debug()"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"scrolled": false
},
"outputs": [
{
"data": {
"text/plain": [
"1596444207"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hs.seed"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment