Yes! That's the trick! Plus a block of ice and a fan to keep the engine block cool! (Although over the long term, the important thing is actually surface area, not thermal mass.)
...Your heatsink is very small so it's not doing much.
It's been awhile since I've done heatsink calculations but you can research it. it's something like Ohm's Law (with thermal resistance/conductivity). You need the specs for the heatsink and you have to consider ambient temperature. (A fan keeps the ambient air near the heatsink from increasing.)
Power dissipation is easy to calculate (4V x 1A = 4W).
I think Data sheet says 1 amp.?
True, but power/heat is usually the limiting factor.
Then i can trash them in the bin and use a mini360 buck converter for my projects instead. Almost same size, does not get hot, can take 2 amp load (at least) and are adjustable. The price is a little higher, but for my home projects its not a big deal. You can get 20pcs mini 360 from AliExpress for 7 dollar.
For the most of my home projects i maybe could used L7805, but i i think mini360 or a little buck converter is a better choice.
The 7805 needs a 0μ33 capacitor at the input and 0μ1 at the output, connected as close to the terminals as possible, with the other end to ground. I don't know if that's the cause of your problem but I believe in fixing whatever is obviously wrong before looking for something else.
The heatsink you have is too small to do anything much. How hot does the 7805 get? Can you put your finger on it without it hurting? While semiconductors can operate at temperatures too hot for humans to touch doing so shortens their life. My rule of thumb is if it's too hot to touch then it's too hot. Remember that the semiconductor itself is inside the package and will be hotter then the temperature of the package.
I tried with capacitors now, and that did'nt help at all. I have decided to use this instead. Almost same size, can take 2.5amp load, does not get wery hot and does not cost wery much.
L7805 is for me just an pretty avfull voltage regulator. I have reed that linear regulators is better for use in audio/radio circuits regards to noise, but other than that i will say a buck converter winns hands down, with good margin.