Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$. 
I want to find $f: \{0,1\}^k \to \{0, 1\}^n$
such that:


1) $f(a) \not= f(b)$ if $a \not=b $


2) for any $x \in \{0,1\}^n$ $V\_x(k/2) \cap Im(f) \le 2^{k(1 - \delta)}$ for some $\delta > 0$, where $V\_x(k/2)$ is a full-sphere with center $x$ and radius $k/2$ (in Hamming's metric ).


3) $f$ can be calculated fast - in polynomial(k) time


Whether there is such $f$?


UPD: $|V\_x(k/2)| \approx 2^{nH((1-\epsilon)/2)}$ By properties of entropy $t: = H((1-\epsilon)/2 < 1$ $|V\_x(k/2)| / |\{0,1\}^n| = 2^{tn}:2^n = 2^{(t-1)n}$. So in "random" full-sphere there $|\{0,1\}^k| \cdot 2^{(t-1)n} < 2^k \cdot 2^{(t-1)k} = 2^{tk} $ points from $Im(f)$ in case of "random" $f$



PRNG and coding theory
Consider the Reed Solomon code with parameters $[n,k,d=n-k+1]$ over the field $\mathbb{F}\_q.$ Take $q=2^m,$ and note that the usual choice is to choose $n=q-1,$ for $q-$ary symbols. Therefore the *binary* length of this code is $N=nm=(2^m-1)m$ while its binary "input length" is $K=km.$


This code is MDS, its full weight distribution (over $\mathbb{F}\_q$) is known but we only need the number of codewords of minimum weight which is $$A\_d=\binom{n}{d}(q-1).$$


Now choose, say, $k=2n/3$ (one can assume $3|n$ ) which gives $d=n/3$.


We use the codewords of this code to define a binary map $$f:\{0,1\}^K\rightarrow \{0,1\}^N.$$


If $x \in Im(f)$ i.e., $x$ is the binary image of a Reed Solomon codeword, there are $$A\_d=A\_{n/3}=\binom{n}{n/3} (q-1)\sim 2^{nH(1/3)+o(n)+m}
\stackrel{(a)}{\sim} 2^{0.92 n+m} =$$


$$=\exp\_2\left\{(nm)\left[0.92/m+o(1/m)+(1/n)\right] \right\}\sim2^{0.92 (3km/2m)}=$$


$$=2^{0.92 (3K/2m)}=2^{1.38 K/m}\leq 2^{K(1-\delta)},\quad \mathrm{for~m~large~enough},$$


codewords within the $K/2$ sphere around it (to justify (a), see the answer [here](https://mathoverflow.net/questions/236508/are-there-good-bounds-on-binomial-coefficients/236511#236511) for the binomial approximation). 


The covering radius of the Reed Solomon codes is known to be $d-1,$ and if $x$ is a point at maximal distance from a codeword, it cannot possibly have more neighbours within the $K/2$ sphere than the number of neighbours of a codeword. This can be verified by using the triangle inequality. This argument also applies to any non-codeword $x,$ thus establishing the claim that PRNG functions satisfying the requirements of the OP exist. 


Note that reed Solomon codewords can be constructed by matrix multiplication or polynomial evaluation, thus with $\mathrm{poly}(n)=\mathrm{poly}(K)$ complexity.


