What are the memory requirements for this type of search if the hash function has an output length n bits? Let us suppose that we perform a collision search to find a pair $x_1$, $x_2$ with $x_1 \neq x_2$ such that $h(x_1)=h(x_2)$ for a given hash function, and we would like to specify the memory requirements for this type of search.

What does memory requirements means in this question ?
The naive approach

A naive algorithm for a research of collision is the following:


choose $x_1$
compute $h(x_1)$
Choose $x_2 \gets x_1 + 1$ ($x_2$ takes the value $x_1 + 1$)
compute $h(x_2)$ and verify if it matches $h(x_1)$
if it does not, do $x_2 \gets x_2 + 1$
go back to step 4, repeat and rinse.


How much memory do we need for this algorithm to work? 
Well we need to store only $x_1$ and $x_2$. You can also store $h(x_1)$ in order to not compute it each time.

So if $h$ has a $b$ bits inputs, you need... $2 \times b$ memory to find your collision ($b$ for $x_1$ and $b$ for $x_2$).
This is the memory requirement for THIS search algorithm.

However this algorithm is clearly inefficient. Assuming the output of your hash function is $n$ bits. You have $2^n$ hash possibles. This will lead to an average of $\frac{2^n}{2}$ tentative... Clearly not feasible with a complexity of $O(2^{n-1})$.

The multi-target attack

In the previous attack we targeted a specific or fixed value ($x_1$). A more advanced attack consist of storing all the previous attempts and each time you try a new value of $x_2$, thus the multi-target.

The algorithm is the following: 


consider an empty list $lst$.
choose $x$
add $x$ to $lst$
Choose $x' \gets x + 1$
Check if there is $x \in lst$ such that $h(x') = h(x)$
Add $x'$ to $lst$
Compute $x' \gets x' + 1$
go back to step 5, repeat and rinse.


I will let you guess the memory requirement for this algorithm.

In term of complexity, if you consider a list of $2^m$ elements, the complexity of this attack is $O(2^{n-m})$.