It is well known that (in suitable codimension) the spaces of long knots in Rn modulo immersions are double loop spaces. Hence the homology carries a natural Gerstenhaber structure, given by the Gerstenhaber structure on the Hochschild homology of the n-Poisson operad. In this paper, we compute the latter Gerstenhaber structure in terms of hairy graphs, and show that it is not quite trivial combinatorially. Curiously, the construction makes essential use of methods and results of deformation quantization, and thus provides a bridge between two previously little related subjects in mathematics.