Crimea or the Autonomous Republic of Crimea. Crimea is a peninsula in the Black Sea, south of Ukraine and west of Russia. The capital is Simferopol. Sovereignty and control of the peninsula became the subject of a territorial dispute between Russia and Ukraine in 2014. The peninsula is now under full control of the Russian Federation, though most other countries consider it part of Ukraine. As a traveler, Crimea is very safe but the political dispute restricts your means of access. As it is now controlled by Russian authorities, you'll need a Russian visa to visit and it is currently only feasible to access on the Kerch ferry via Russia (the border with Ukraine is only open to those with Ukrainian passports or those with a special permit which in most circumstances is more difficult to get than just going through Russia).The ferry costs 150 Rubles ($3, May 2017) each way and passengers pay separately from cars so it's not easy to hitchhike on. Entering Crimea via Russia is illegal according to Ukrainian laws, but there is no way the Ukrainian authorities would ever know as long as you exit Crimea back through Russia. You'll have to show your passport to buy the ferry ticket, but there is no border control or anything between Russia and Crimea.
Especially in summer certain parts of the peninsula are full of tourists, mainly from Russia. Along with plenty of beaches, Crimea has a very rich history. It's well worth exploring the southeast coast where mountains meet the sea, and the many historical landmarks scattered throughout the territory. If you're curious about people's opinions on Russia/Ukraine, it's advisable to do more listening than talking, or at least understand your driver's stance before you state your own opinion. A majority of Crimeans are very happy to be a part of Russia and will be even happier to tell you about that, but certainly not everybody has this mindset.
n0id found warnings of slow hitchhiking to be incorrect. Experience showed that hitchhiking is not difficult at all. A few times people stopped and asked for money, but disappeared quite quickly when told we were hitchhiking. Some of the people picking us up were wondering why we were hitchhiking at all and referring to the cheap buses. Due to tourism, there are very good & reasonably cheap bus connections between the cities in the Southern part. However, it is probably indeed better to hitchhike in the inside of the country than on the road along the coast, since there we waited the longest. User:TBF would absolutely recommend hitchhiking in Crimea; it was far easier to hitchhike in Crimea than any other part of Ukraine and was comparable to the rest of Western Russia. Even hitchhiking with two males, we were almost always picked up within 15 minutes and saw many other hitchhikers on the road (May 2017).
Sleeping in a tent is usually no problem outside of cities. You can camp on many beaches along the coast, although in the touristy parts some beaches are not for free. Only between Nikita and Sevastopol it is said to be more difficult, since there are many resorts and private beaches which could make it harder to camp out directly at the sea. If you look, you'll always find a place, though. There are also very interesting abandoned catacombs to explore and camp in/near. One entrance is just a few hundred meters east of the village Kamenskoe. On hot summer days, the catacombs are always cool and the entrance provides a nice place to set up a tent without baking in the sun.