Even when over the ocean, someone is responsible for communications there. Over the Pacific we talk to Oakland, San Francisco or Tokyo on our route network, depending on where in the Pacific you are. Flying down to Johannesburg from Hong Kong you might be speaking to Bombay, Antananarivo, Beira. It all depends on what country is responsible for that area. Each of these areas have their own set of HF frequencies printed on the charts that you can try. Normally when one ATC unit hands you off to another, they will tell you what frequencies are in use. Sometimes various ATC areas use the same frequency, so you need to wait your turn and then talk. Some people just talk over the others in the hope that the person who talks the loudest will win! It's a big like a dogfight of the airwaves, especially when flying in the Indian Ocean, when Bombay seems to reply to everyone, even when you are talking to Calcutta, Colombo, 'Tana', or Beira.
Thankfully these days many aircraft and ATC areas have something called CPDLC (If I remember, Controller Pilot Data Link Communication or similar). We can then logon our FMC to their computers and just press 'send' on an FMC page with all our position report information on, and they receive it on their screens. It's all very easy to use and slowly more and more countries are getting it. One day HF communication may be a thing of the past, although sometimes it does help pass the time away on those long boring nights.