{
    "info": {
        "author": "blester125",
        "author_email": "blester125@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 3 - Alpha",
            "Environment :: Console",
            "Intended Audience :: Developers",
            "Intended Audience :: Science/Research",
            "License :: OSI Approved :: MIT License",
            "Natural Language :: English",
            "Programming Language :: Python :: 3 :: Only",
            "Topic :: Scientific/Engineering"
        ],
        "description": "# Prehashed\n\n[<img src=\"https://travis-ci.com/blester125/prehashed.svg?branch=master\" alt=\"Build Status\">](https://travis-ci.com/blester125/prehashed)\n\nA python dictionary that hashes keys before they are inserted to the dict. This yields substantial memory savings when the keys of a dictionary are quite large (for example long stings).\n\nThe point of this is that we can store keys that are really large (long strings) cheaply. For example when storing the documents in the tokenized Dailymail dataset the keys take up 1.018 GB while this implementation takes 10.53 MB. A small space saving (7.79 MB vs 10.53 MB) can be found using the built in `hash` function but the results of this are not shareable across runs because python changes the seed across runs.\n\n### Collisions\n\nObviously we want to know __What is the probability that I will have a hash collision?__. We can figure this out by asking the reverse. What is the probability that all of keys are unique? Once we have this we can answer the original question by subtracting this from 1.\n\nGiven N possible hash values (`2 ** 160` for sha1) we know the first hash will be unique, Then for the second one we know there are `N - 1` hashes we could use and still be unique, this means our probability is `N - 1 / N`. This continues for `N - 2, 3` etc. So if we are hashing `k` keys we can find the probability of them all being unique with `PI i=1 -> k-1 (N - i) / N`. This can be approximated with `e^((-k * (k - 1)) / (2 * N))`. This can be further approximated with (k * (k - 1) / (2 * N)) for small k because `1 - e^x ~= x` and when N is 2 ** 160 most k is small.\n\nGraph\n\nTo sum this up here is a table with some of the probabilities of your keys colliding.\n\n| k | Odds |\n| - | ---- |\n|`1.71x10^15` | `1 in 10 ^ 18` |\n|`1.71x10^19` | `1 in 10 billion` |\n|`1.71x10^21` | `1 in a million` |\n|`1.71x10^23` | `1 in 100` |\n|`1.42x10^24` | `1 in 2` |\n\nSo unless you plan use put `171,000,000,000,000,000,000,000` keys into this dict or people will die if your code has bugs I wouldn't worry about collisions.\n\nThere is a small chance that keys will collide. When this happens this dictionary cannot detect that and as a result these keys will overwrite each other. This is so rare that git doesn't have a mitigation strategy either.\n\nWhile a collisions are super rare if you are worried about it I would suggest that all of your values are the same type so that you aren't expecting a string and get an int in the super unlikely case if a collision.\n\nIf you are still scared about collisions there is also a function `initial_add(k, v)` that will modify your key until it doesn't have a collision, adds it to the dictionary, and returns the new key to use. You need to keep this key to get the value later so this kind of breaks the point of this dict where you want to be able to throw away your keys.",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "https://github.com/blester125/prehashed/archive/1.0.1.tar.gz",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/blester125/prehashed",
        "keywords": "",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "prehashed",
        "package_url": "https://pypi.org/project/prehashed/",
        "platform": "",
        "project_url": "https://pypi.org/project/prehashed/",
        "project_urls": {
            "Download": "https://github.com/blester125/prehashed/archive/1.0.1.tar.gz",
            "Homepage": "https://github.com/blester125/prehashed"
        },
        "release_url": "https://pypi.org/project/prehashed/1.0.1/",
        "requires_dist": null,
        "requires_python": ">=3.6",
        "summary": "Prehashing keys for memory saving.",
        "version": "1.0.1"
    },
    "last_serial": 3904022,
    "releases": {
        "0.0.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "9d4218a94bf27aea8e301232c7a8e61b",
                    "sha256": "7bbe743594a5569192d7e7c9bc02ccf238b5783ef843e3582018fa800473b7f3"
                },
                "downloads": -1,
                "filename": "prehashed-0.0.0.tar.gz",
                "has_sig": false,
                "md5_digest": "9d4218a94bf27aea8e301232c7a8e61b",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": ">=3.6",
                "size": 1794,
                "upload_time": "2018-05-24T03:35:30",
                "url": "https://files.pythonhosted.org/packages/e0/43/031336133eaa2774873eee38d76b46bdd1f17a292f7d61e79ad60eb977be/prehashed-0.0.0.tar.gz"
            }
        ],
        "1.0.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "c081370ba9588a3450d6fe0b9f4f53f1",
                    "sha256": "2c9fcdcdab8344370975d91732f784e3615476a396658ca111730490b0993527"
                },
                "downloads": -1,
                "filename": "prehashed-1.0.0.tar.gz",
                "has_sig": false,
                "md5_digest": "c081370ba9588a3450d6fe0b9f4f53f1",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": ">=3.6",
                "size": 4136,
                "upload_time": "2018-05-24T23:34:57",
                "url": "https://files.pythonhosted.org/packages/ff/b2/e1f116479a7b25c67c2a594134fd155d03486109d4643e319483b08d16a8/prehashed-1.0.0.tar.gz"
            }
        ],
        "1.0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "81b5287334a49e1eb08463ede7d3ae22",
                    "sha256": "7fb85333e2ee61daefe8ae6ea12bd4de6bff9112dc8aafa0cf3900a0d8e289de"
                },
                "downloads": -1,
                "filename": "prehashed-1.0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "81b5287334a49e1eb08463ede7d3ae22",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": ">=3.6",
                "size": 4097,
                "upload_time": "2018-05-27T20:55:56",
                "url": "https://files.pythonhosted.org/packages/83/86/5eccc452eb91a4a13b224ad54007a1b61df3f538830775e4337b1b4774e6/prehashed-1.0.1.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "81b5287334a49e1eb08463ede7d3ae22",
                "sha256": "7fb85333e2ee61daefe8ae6ea12bd4de6bff9112dc8aafa0cf3900a0d8e289de"
            },
            "downloads": -1,
            "filename": "prehashed-1.0.1.tar.gz",
            "has_sig": false,
            "md5_digest": "81b5287334a49e1eb08463ede7d3ae22",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.6",
            "size": 4097,
            "upload_time": "2018-05-27T20:55:56",
            "url": "https://files.pythonhosted.org/packages/83/86/5eccc452eb91a4a13b224ad54007a1b61df3f538830775e4337b1b4774e6/prehashed-1.0.1.tar.gz"
        }
    ]
}