Duplicate of https://stackoverflow.com/questions/3675728/expected-collisions-for-perfect-32bit-crc

The answer referenced this article: http://arstechnica.com/civis/viewtopic.php?f=20&amp;t=149670

Found the image below from: http://preshing.com/20110504/hash-collision-probabilities

![enter image description here][1]


  [1]: http://i.stack.imgur.com/u4DeG.png

In the case you cite, at least one collision is essentially guaranteed.  The probability of at least one collision is about 1 - 3x10&lt;sup&gt;-51&lt;/sup&gt;.  The average number of collisions you would expect is about 116.

In general, the average number of collisions in _k_ samples, each a random choice among _n_ possible values is:

![N(n,k)~=k(k-1)/(2n)][1]

The probability of at least one collision is:

![p(n,k)~=1-e^(-k(k-1)/(2n))][2]

In your case, _n_ = 2&lt;sup&gt;32&lt;/sup&gt; and _k_ = 10&lt;sup&gt;6&lt;/sup&gt;.

The probability of a _three_-way collision in your case is about 0.01.  See the [Birthday Problem][3].


  [1]: http://i.stack.imgur.com/HuSas.png
  [2]: http://i.stack.imgur.com/n1cra.png
  [3]: http://en.wikipedia.org/wiki/Birthday_problem

I am facing a problem with **overlaying a 100% height div**. I could use position fixed to solve the cover, but that&#39;s not really what I want because you should be able to scroll down on the &#39;cover&#39; &gt; so people with lower resolutions than mine can see the entire content.

Code example:

HTML

    &lt;body&gt;
    &lt;div&gt;Overlay example text&lt;/div&gt;
    &lt;/body&gt;
CSS

    body {
        float: left;
        height: 3000px;
        width: 100%;
    }
    body div {
        position: absolute;
        height: 100%;
        width: 100%;
        background-color: yellow;
    }

**The problem:** The div&#39;s height 100% only contains 100% of the webbrowser/viewport, but I want it to cover the entire body.

Thanks in advance :)

Set height 100% on absolute div

In Python, how do I pick which Parent&#39;s method to call? Say I want to call the parent ASDF2&#39;s `__init__` method. Seems like I have to specify __ASDF1__ in the super()..? And if I want to call ASDF3&#39;s `__init__`, then I must specify __ASDF2__?!

    &gt;&gt;&gt; class ASDF(ASDF1, ASDF2, ASDF3):
    	def __init__(self):
    		super(ASDF1, self).__init__()
    
    		
    &gt;&gt;&gt; ASDF()
    ASDF2&#39;s __init__ happened
    &gt;&gt;&gt; class ASDF(ASDF1, ASDF2, ASDF3):
    	def __init__(self):
    		super(ASDF2, self).__init__()
    
    		
    &gt;&gt;&gt; ASDF()
    ASDF3&#39;s __init__ happened

Seems bonkers to me. What am I doing wrong?

Python&#39;s Multiple Inheritance: Picking which super() to call

I have a 10 character string key field in a database. I&#39;ve used CRC32 to hash this field but I&#39;m worry about duplicates. Could somebody show me the probability of collision in this situation?

p.s. my string field is unique in the database. If the number of string fields is 1 million, what is probability of collision ?

Probability of collision when using a 32 bit hash

<p>I have a 10 character string key field in a database. I've used CRC32 to hash this field but I'm worry about duplicates. Could somebody show me the probability of collision in this situation?</p>
<p>p.s. my string field is unique in the database. If the number of string fields is 1 million, what is probability of collision ?</p>


Algorithm solution:

	std::generate(numbers.begin(), numbers.end(), rand);

Range-based for-loop solution:

	for (int&amp; x : numbers) x = rand();

Why would I want to use the more verbose `std::generate` over range-based for-loops in C++11?

Does the range-based &#39;for&#39; loop deprecate many simple algorithms?

I was trying various methods to implement a program that gives the digits of pi sequentially. I tried the [Taylor series][1] method, but it proved to converge extremely slowly (when I compared my result with the online values after some time). Anyway, I am trying better algorithms.

So, while writing the program I got stuck on a problem, as with all algorithms: How do I know that the `n` digits that I&#39;ve calculated are accurate?

  [1]: http://en.wikipedia.org/wiki/Taylor_series



How do I determine whether my calculation of pi is accurate?

I am reading the definitions of radix, counting and bucket sorts and it seems that all of them are just the code below:
    
    public static void sort(int[] a, int maxVal){
        int [] bucket=new int[maxVal+1];

        for (int i=0; i&lt;bucket.length; i++){
            bucket[i]=0;
        }

        for (int i=0; i&lt;a.length; i++){
            bucket[a[i]]++;
        }

        int outPos=0;
        for (int i=0; i&lt;bucket.length; i++){
            for (int j=0; j&lt;bucket[i]; j++){
                a[outPos++]=i;
            }
        }
    }

I know I can&#39;t be right, so what am I missing? Show the code if you think that can help explaining in Java or C.

Radix sort vs Counting sort vs Bucket sort. What&#39;s the difference?

Yesterday I was pairing the socks from the clean laundry and figured out the way I was doing it is not very efficient. I was doing a naive search&amp;nbsp;— picking one sock and &quot;iterating&quot; the pile in order to find its pair. This requires iterating over n/2 * n/4 = n&lt;sup&gt;2&lt;/sup&gt;/8 socks on average.

As a computer scientist I was thinking what I could do? Sorting (according to size/color/...) of course came to mind to achieve an O(NlogN) solution.

Hashing or other not-in-place solutions are not an option, because I am not able to duplicate my socks (though it could be nice if I could).

**So, the question is basically:**

Given a pile of `n` pairs of socks, containing `2n` elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space? (I believe I can remember that amount of info if needed.)

I will appreciate an answer that addresses the following aspects:

 - A general *theoretical* solution for a huge number of socks.
 - The actual number of socks is not that large, I don&#39;t believe my spouse and I have more than 30 pairs. (And it is fairly easy to distinguish between my socks and hers; can this be used as well?)
 - Is it equivalent to the [element distinctness problem][1]?

  [1]: http://en.wikipedia.org/wiki/Element_distinctness_problem



How can I pair socks from a pile efficiently?

I have a list of lists and I am sorting them using the following 

    data=sorted(data, key=itemgetter(0))

Was wondering what is the runtime complexity of this python function?

 

What is the complexity of the sorted() function?

I have a 2D array of Integers. I want them to be put into a HashMap. But I want to access the elements from the HashMap based on Array Index. Something like:

For A[2][5], `map.get(2,5)` which returns a value associated with that key. But how do I create a hashMap with a pair of keys? Or in general, multiple keys: `Map&lt;((key1, key2,..,keyN), Value)` in a way that I can access the element with using get(key1,key2,...keyN).
 

**EDIT :  3 years after posting the question, I want to add a bit more to it**

I came across another way for `NxN matrix`. 

Array indices, `i` and `j` can be represented as a single `key` the following way:

    int key = i * N + j;
    //map.put(key, a[i][j]); // queue.add(key); 

And the indices can be retrevied from the `key` in this way:

    int i = key / N;
    int j = key % N;





How to create a HashMap with two keys (Key-Pair, Value)?

I downloaded and extracted Crypto++ in C:\cryptopp. I used Visual Studio Express 2012 to build all the projects inside (as instructed in readme), and everything was built successfully. Then I made a test project in some other folder and added cryptolib as a dependency. After that, I added the include path so I can easily include all the headers. When I tried to compile, I got an error about unresolved symbols.

To remedy that, I added `C:\cryptopp\Win32\Output\Debug\cryptlib.lib` to link additional dependencies. Now I get this error:

    Error	1	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(cryptlib.obj)	CryptoTest
    Error	2	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(iterhash.obj)	CryptoTest
    Error	3	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(sha.obj)	CryptoTest
    Error	4	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(pch.obj)	CryptoTest
    Error	5	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(misc.obj)	CryptoTest
    Error	6	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(queue.obj)	CryptoTest
    Error	7	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(algparam.obj)	CryptoTest
    Error	8	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(filters.obj)	CryptoTest
    Error	9	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(fips140.obj)	CryptoTest
    Error	10	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(cpu.obj)	CryptoTest
    Error	11	error LNK2038: mismatch detected for &#39;RuntimeLibrary&#39;: value &#39;MTd_StaticDebug&#39; doesn&#39;t match value &#39;MDd_DynamicDebug&#39; in program.obj	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\cryptlib.lib(mqueue.obj)	CryptoTest


I also get:


    Error	12	error LNK2005: &quot;public: __thiscall std::_Container_base12::_Container_base12(void)&quot; (??0_Container_base12@std@@QAE@XZ) already defined in cryptlib.lib(cryptlib.obj)	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\msvcprtd.lib(MSVCP110D.dll)	CryptoTest
    Error	13	error LNK2005: &quot;public: __thiscall std::_Container_base12::~_Container_base12(void)&quot; (??1_Container_base12@std@@QAE@XZ) already defined in cryptlib.lib(cryptlib.obj)	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\msvcprtd.lib(MSVCP110D.dll)	CryptoTest
    Error	14	error LNK2005: &quot;public: void __thiscall std::_Container_base12::_Orphan_all(void)&quot; (?_Orphan_all@_Container_base12@std@@QAEXXZ) already defined in cryptlib.lib(cryptlib.obj)	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\msvcprtd.lib(MSVCP110D.dll)	CryptoTest
    Error	15	error LNK2005: &quot;public: __thiscall std::locale::id::id(unsigned int)&quot; (??0id@locale@std@@QAE@I@Z) already defined in cryptlib.lib(iterhash.obj)	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\msvcprtd.lib(MSVCP110D.dll)	CryptoTest
    Warning	16	warning LNK4098: defaultlib &#39;LIBCMTD&#39; conflicts with use of other libs; use /NODEFAULTLIB:library	C:\Data\Work\C++ VS\CryptoTest\CryptoTest\LINK	CryptoTest
    Error	17	error LNK1169: one or more multiply defined symbols found	C:\Data\Work\C++ VS\CryptoTest\Debug\CryptoTest.exe	1	1	CryptoTest

The code I tried to compile was simple (I got this from another site):

    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &quot;sha.h&quot;
    #include &quot;hex.h&quot;
    using namespace std;
    
    string SHA256(string data) {
        byte const* pbData = (byte*) data.data();
        unsigned int nDataLen = data.size();
        byte abDigest[32];
    
        CryptoPP::SHA256().CalculateDigest(abDigest, pbData, nDataLen);
    
        return string((char*)abDigest);
    }
    
    int main(void) {
    
    	return 0;
    }

Any ideas how to fix this? I really only need SHA-256 right now, nothing else.
I am using Windows 7 64 bit, and I downloaded VS C++ today, so it should be the newest version.

Mismatch Detected for &#39;RuntimeLibrary&#39;

How to write `functionToGenerateMD5hash` for this code? I already have `fileVideo` and I need to send the corresponding md5 hash to the server by clicking on the button.

    $(&quot;#someButton&quot;).click(function() {
    var fr = new FileReader();      
    fr.onload = function(e) {            
        string md5 = functionToGenerateMD5hash(e.target.result);
        // send md5 here
    };       
    fr.readAsArrayBuffer(fileVideo);

Also, can you use this to generate a MD5 hash in Node.js?

How to generate an MD5 file hash in JavaScript/Node.js?

I&#39;m just curious because I guess it will have impact on performance. Does it consider the full string? If yes, it will be slow on long string. If it only consider part of the string, it will have bad performance (e.g. if it only consider the beginning of the string, it will have bad performance if a HashSet contains mostly strings with the same.

How is GetHashCode() of C# string implemented?

I am using code `$enrypt=md5($pass)` and inserting `$encrypt` to database. I want to find out a way to decrypt them. I tried using a  decrypting software but it says the hash should be of exactly 16 bytes. is there any way to decrypt it or to make it a 16 byte md5 hash?

My hash looks like this: `c4ca4238a0b923820dcc`

encrypt and decrypt md5

I&#39;ve been working on adding a Quadtree to a program that I&#39;m writing, and I can&#39;t help but notice that there are few well explained/performing tutorials for the implementation that I&#39;m looking for.

Specifically, a list of the methods and pseudocode for how to implement them (or just a description of their processes) that are commonly used in a Quadtree (retrieve, insert, remove, etc.) is what I&#39;m looking for, along with maybe some tips to improve performance. This is for collision detection, so it&#39;d be best to be explained with 2d rectangles in mind, as they are the objects that will be stored.

Efficient (and well explained) implementation of a Quadtree for 2D collision detection

How do I get the probability of a string being similar to another string in Python?

I want to get a decimal value like 0.9 (meaning 90%) etc. Preferably with standard Python and library.

e.g.

    similar(&quot;Apple&quot;,&quot;Appel&quot;) #would have a high prob.
    
    similar(&quot;Apple&quot;,&quot;Mango&quot;) #would have a lower prob.



Find the similarity metric between two strings

I am wondering what would be the best way (e.g. in Java) to generate random numbers within a particular range where each number has a certain probability to occur or not?

e.g.

Generate random integers from within [1;3] with the following probabilities:

P(1) = 0.2&lt;br&gt;
P(2) = 0.3&lt;br&gt;
P(3) = 0.5&lt;br&gt;

----------

Right now I am considering the approach to generate a random integer within [0;100] and do the following:

If it is within [0;20] --&gt; I got my random number 1.&lt;br&gt;
If it is within [21;50] --&gt; I got my random number 2.&lt;br&gt;
If it is within [51;100] --&gt; I got my random number 3.&lt;br&gt;
&lt;br&gt;
What would you say?

Random number with Probabilities

I need to normalize a list of values to fit in a probability distribution, i.e. between 0.0 and 1.0.

I understand *how* to normalize, but was curious if Python had a function to automate this.

I&#39;d like to go from:

    raw = [0.07, 0.14, 0.07]  
to  

    normed = [0.25, 0.50, 0.25]

Normalizing a list of numbers in Python

**Edit:** So basically what I&#39;m trying to write is a 1 bit hash for `double`.

I want to map a `double` to `true` or `false` with a 50/50 chance. For that I wrote code that picks some random numbers *(just as an example, I want to use this on data with regularities and still get a 50/50 result)*, checks their last bit and increments `y` if it is 1, or `n` if it is 0. 

However, this code constantly results in 25% `y` and 75% `n`. Why is it not 50/50? And why such a weird, but straight-forward (1/3) distribution?

    public class DoubleToBoolean {
    	@Test
    	public void test() {
    
    		int y = 0;
    		int n = 0;
    		Random r = new Random();
    		for (int i = 0; i &lt; 1000000; i++) {
    			double randomValue = r.nextDouble();
    			long lastBit = Double.doubleToLongBits(randomValue) &amp; 1;
    			if (lastBit == 1) {
    				y++;
    			} else {
    				n++;
    			}
    		}
    		System.out.println(y + &quot; &quot; + n);
    	}
    }

Example output:

    250167 749833

Content Type	Original Author	Original Content on Stackoverflow
Question	nguyenngoc101	View Question on Stackoverflow
Solution 1 - Algorithm	Adam Morris	View Answer on Stackoverflow
Solution 2 - Algorithm	Mark Adler	View Answer on Stackoverflow

Probability of collision when using a 32 bit hash

Algorithm Problem Overview

Algorithm Solutions

Solution 1 - Algorithm

Solution 2 - Algorithm

Python's Multiple Inheritance: Picking which super() to call

Set height 100% on absolute div

Attributions