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
}